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