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