|
0
|
1 /*
|
|
|
2 * Copyright 1997-2005 Sun Microsystems, Inc. All Rights Reserved.
|
|
|
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 {
|
|
|
186 // Save parent (currernt top block on stack) in DFS
|
|
|
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.
|
|
|
399 void PhaseIdealLoop::Dominators( ) {
|
|
|
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.
|
|
|
457 if( whead->is_Region() ) {
|
|
|
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
|
