Mercurial > hg > graal-compiler
annotate src/share/vm/opto/domgraph.cpp @ 3992:d1bdeef3e3e2
7098282: G1: assert(interval >= 0) failed: Sanity check, referencePolicy.cpp: 76
Summary: There is a race between one thread successfully forwarding and copying the klass mirror for the SoftReference class (including the static master clock) and another thread attempting to use the master clock while attempting to discover a soft reference object. Maintain a shadow copy of the soft reference master clock and use the shadow during reference discovery and reference processing.
Reviewed-by: tonyp, brutisso, ysr
author | johnc |
---|---|
date | Wed, 12 Oct 2011 10:25:51 -0700 |
parents | f95d63e2154a |
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 |