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