1.1 --- a/src/share/vm/opto/domgraph.cpp Thu Aug 15 11:59:19 2013 -0700
1.2 +++ b/src/share/vm/opto/domgraph.cpp Fri Aug 16 10:23:55 2013 +0200
1.3 @@ -32,9 +32,6 @@
1.4
1.5 // Portions of code courtesy of Clifford Click
1.6
1.7 -// Optimization - Graph Style
1.8 -
1.9 -//------------------------------Tarjan-----------------------------------------
1.10 // A data structure that holds all the information needed to find dominators.
1.11 struct Tarjan {
1.12 Block *_block; // Basic block for this info
1.13 @@ -60,23 +57,21 @@
1.14
1.15 };
1.16
1.17 -//------------------------------Dominator--------------------------------------
1.18 // Compute the dominator tree of the CFG. The CFG must already have been
1.19 // constructed. This is the Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
1.20 -void PhaseCFG::Dominators( ) {
1.21 +void PhaseCFG::build_dominator_tree() {
1.22 // Pre-grow the blocks array, prior to the ResourceMark kicking in
1.23 - _blocks.map(_num_blocks,0);
1.24 + _blocks.map(number_of_blocks(), 0);
1.25
1.26 ResourceMark rm;
1.27 // Setup mappings from my Graph to Tarjan's stuff and back
1.28 // Note: Tarjan uses 1-based arrays
1.29 - Tarjan *tarjan = NEW_RESOURCE_ARRAY(Tarjan,_num_blocks+1);
1.30 + Tarjan* tarjan = NEW_RESOURCE_ARRAY(Tarjan, number_of_blocks() + 1);
1.31
1.32 // Tarjan's algorithm, almost verbatim:
1.33 // Step 1:
1.34 - _rpo_ctr = _num_blocks;
1.35 - uint dfsnum = DFS( tarjan );
1.36 - if( dfsnum-1 != _num_blocks ) {// Check for unreachable loops!
1.37 + uint dfsnum = do_DFS(tarjan, number_of_blocks());
1.38 + if (dfsnum - 1 != number_of_blocks()) { // Check for unreachable loops!
1.39 // If the returned dfsnum does not match the number of blocks, then we
1.40 // must have some unreachable loops. These can be made at any time by
1.41 // IterGVN. They are cleaned up by CCP or the loop opts, but the last
1.42 @@ -93,14 +88,13 @@
1.43 C->record_method_not_compilable("unreachable loop");
1.44 return;
1.45 }
1.46 - _blocks._cnt = _num_blocks;
1.47 + _blocks._cnt = number_of_blocks();
1.48
1.49 // Tarjan is using 1-based arrays, so these are some initialize flags
1.50 tarjan[0]._size = tarjan[0]._semi = 0;
1.51 tarjan[0]._label = &tarjan[0];
1.52
1.53 - uint i;
1.54 - for( i=_num_blocks; i>=2; i-- ) { // For all vertices in DFS order
1.55 + for (uint i = number_of_blocks(); i >= 2; i--) { // For all vertices in DFS order
1.56 Tarjan *w = &tarjan[i]; // Get vertex from DFS
1.57
1.58 // Step 2:
1.59 @@ -130,19 +124,19 @@
1.60 }
1.61
1.62 // Step 4:
1.63 - for( i=2; i <= _num_blocks; i++ ) {
1.64 + for (uint i = 2; i <= number_of_blocks(); i++) {
1.65 Tarjan *w = &tarjan[i];
1.66 if( w->_dom != &tarjan[w->_semi] )
1.67 w->_dom = w->_dom->_dom;
1.68 w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later
1.69 }
1.70 // No immediate dominator for the root
1.71 - Tarjan *w = &tarjan[_broot->_pre_order];
1.72 + Tarjan *w = &tarjan[get_root_block()->_pre_order];
1.73 w->_dom = NULL;
1.74 w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later
1.75
1.76 // Convert the dominator tree array into my kind of graph
1.77 - for( i=1; i<=_num_blocks;i++){// For all Tarjan vertices
1.78 + for(uint i = 1; i <= number_of_blocks(); i++){ // For all Tarjan vertices
1.79 Tarjan *t = &tarjan[i]; // Handy access
1.80 Tarjan *tdom = t->_dom; // Handy access to immediate dominator
1.81 if( tdom ) { // Root has no immediate dominator
1.82 @@ -152,11 +146,10 @@
1.83 } else
1.84 t->_block->_idom = NULL; // Root
1.85 }
1.86 - w->setdepth( _num_blocks+1 ); // Set depth in dominator tree
1.87 + w->setdepth(number_of_blocks() + 1); // Set depth in dominator tree
1.88
1.89 }
1.90
1.91 -//----------------------------Block_Stack--------------------------------------
1.92 class Block_Stack {
1.93 private:
1.94 struct Block_Descr {
1.95 @@ -214,7 +207,6 @@
1.96 }
1.97 };
1.98
1.99 -//-------------------------most_frequent_successor-----------------------------
1.100 // Find the index into the b->succs[] array of the most frequent successor.
1.101 uint Block_Stack::most_frequent_successor( Block *b ) {
1.102 uint freq_idx = 0;
1.103 @@ -258,40 +250,38 @@
1.104 return freq_idx;
1.105 }
1.106
1.107 -//------------------------------DFS--------------------------------------------
1.108 // Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup
1.109 // 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent.
1.110 -uint PhaseCFG::DFS( Tarjan *tarjan ) {
1.111 - Block *b = _broot;
1.112 +uint PhaseCFG::do_DFS(Tarjan *tarjan, uint rpo_counter) {
1.113 + Block* root_block = get_root_block();
1.114 uint pre_order = 1;
1.115 - // Allocate stack of size _num_blocks+1 to avoid frequent realloc
1.116 - Block_Stack bstack(tarjan, _num_blocks+1);
1.117 + // Allocate stack of size number_of_blocks() + 1 to avoid frequent realloc
1.118 + Block_Stack bstack(tarjan, number_of_blocks() + 1);
1.119
1.120 // Push on stack the state for the first block
1.121 - bstack.push(pre_order, b);
1.122 + bstack.push(pre_order, root_block);
1.123 ++pre_order;
1.124
1.125 while (bstack.is_nonempty()) {
1.126 if (!bstack.last_successor()) {
1.127 // Walk over all successors in pre-order (DFS).
1.128 - Block *s = bstack.next_successor();
1.129 - if (s->_pre_order == 0) { // Check for no-pre-order, not-visited
1.130 + Block* next_block = bstack.next_successor();
1.131 + if (next_block->_pre_order == 0) { // Check for no-pre-order, not-visited
1.132 // Push on stack the state of successor
1.133 - bstack.push(pre_order, s);
1.134 + bstack.push(pre_order, next_block);
1.135 ++pre_order;
1.136 }
1.137 }
1.138 else {
1.139 // Build a reverse post-order in the CFG _blocks array
1.140 Block *stack_top = bstack.pop();
1.141 - stack_top->_rpo = --_rpo_ctr;
1.142 + stack_top->_rpo = --rpo_counter;
1.143 _blocks.map(stack_top->_rpo, stack_top);
1.144 }
1.145 }
1.146 return pre_order;
1.147 }
1.148
1.149 -//------------------------------COMPRESS---------------------------------------
1.150 void Tarjan::COMPRESS()
1.151 {
1.152 assert( _ancestor != 0, "" );
1.153 @@ -303,14 +293,12 @@
1.154 }
1.155 }
1.156
1.157 -//------------------------------EVAL-------------------------------------------
1.158 Tarjan *Tarjan::EVAL() {
1.159 if( !_ancestor ) return _label;
1.160 COMPRESS();
1.161 return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;
1.162 }
1.163
1.164 -//------------------------------LINK-------------------------------------------
1.165 void Tarjan::LINK( Tarjan *w, Tarjan *tarjan0 ) {
1.166 Tarjan *s = w;
1.167 while( w->_label->_semi < s->_child->_label->_semi ) {
1.168 @@ -333,7 +321,6 @@
1.169 }
1.170 }
1.171
1.172 -//------------------------------setdepth---------------------------------------
1.173 void Tarjan::setdepth( uint stack_size ) {
1.174 Tarjan **top = NEW_RESOURCE_ARRAY(Tarjan*, stack_size);
1.175 Tarjan **next = top;
1.176 @@ -362,8 +349,7 @@
1.177 } while (last < top);
1.178 }
1.179
1.180 -//*********************** DOMINATORS ON THE SEA OF NODES***********************
1.181 -//------------------------------NTarjan----------------------------------------
1.182 +// Compute dominators on the Sea of Nodes form
1.183 // A data structure that holds all the information needed to find dominators.
1.184 struct NTarjan {
1.185 Node *_control; // Control node associated with this info
1.186 @@ -396,7 +382,6 @@
1.187 #endif
1.188 };
1.189
1.190 -//------------------------------Dominator--------------------------------------
1.191 // Compute the dominator tree of the sea of nodes. This version walks all CFG
1.192 // nodes (using the is_CFG() call) and places them in a dominator tree. Thus,
1.193 // it needs a count of the CFG nodes for the mapping table. This is the
1.194 @@ -517,7 +502,6 @@
1.195 }
1.196 }
1.197
1.198 -//------------------------------DFS--------------------------------------------
1.199 // Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup
1.200 // 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent.
1.201 int NTarjan::DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder) {
1.202 @@ -560,7 +544,6 @@
1.203 return dfsnum;
1.204 }
1.205
1.206 -//------------------------------COMPRESS---------------------------------------
1.207 void NTarjan::COMPRESS()
1.208 {
1.209 assert( _ancestor != 0, "" );
1.210 @@ -572,14 +555,12 @@
1.211 }
1.212 }
1.213
1.214 -//------------------------------EVAL-------------------------------------------
1.215 NTarjan *NTarjan::EVAL() {
1.216 if( !_ancestor ) return _label;
1.217 COMPRESS();
1.218 return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;
1.219 }
1.220
1.221 -//------------------------------LINK-------------------------------------------
1.222 void NTarjan::LINK( NTarjan *w, NTarjan *ntarjan0 ) {
1.223 NTarjan *s = w;
1.224 while( w->_label->_semi < s->_child->_label->_semi ) {
1.225 @@ -602,7 +583,6 @@
1.226 }
1.227 }
1.228
1.229 -//------------------------------setdepth---------------------------------------
1.230 void NTarjan::setdepth( uint stack_size, uint *dom_depth ) {
1.231 NTarjan **top = NEW_RESOURCE_ARRAY(NTarjan*, stack_size);
1.232 NTarjan **next = top;
1.233 @@ -631,7 +611,6 @@
1.234 } while (last < top);
1.235 }
1.236
1.237 -//------------------------------dump-------------------------------------------
1.238 #ifndef PRODUCT
1.239 void NTarjan::dump(int offset) const {
1.240 // Dump the data from this node
