2
* Copyright (c) 1997, 2024, Oracle and/or its affiliates. All rights reserved.
3
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
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.
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).
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.
19
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20
* or visit www.oracle.com if you need additional information or have any
25
#include "precompiled.hpp"
26
#include "libadt/vectset.hpp"
27
#include "memory/allocation.hpp"
28
#include "memory/resourceArea.hpp"
29
#include "opto/block.hpp"
30
#include "opto/machnode.hpp"
31
#include "opto/phaseX.hpp"
32
#include "opto/rootnode.hpp"
34
// Portions of code courtesy of Clifford Click
36
// A data structure that holds all the information needed to find dominators.
38
Block *_block; // Basic block for this info
40
uint _semi; // Semi-dominators
41
uint _size; // Used for faster LINK and EVAL
42
Tarjan *_parent; // Parent in DFS
43
Tarjan *_label; // Used for LINK and EVAL
44
Tarjan *_ancestor; // Used for LINK and EVAL
45
Tarjan *_child; // Used for faster LINK and EVAL
46
Tarjan *_dom; // Parent in dominator tree (immediate dom)
47
Tarjan *_bucket; // Set of vertices with given semidominator
49
Tarjan *_dom_child; // Child in dominator tree
50
Tarjan *_dom_next; // Next in dominator tree
52
// Fast union-find work
55
void LINK( Tarjan *w, Tarjan *tarjan0 );
57
void setdepth( uint size );
61
// Compute the dominator tree of the CFG. The CFG must already have been
62
// constructed. This is the Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
63
void PhaseCFG::build_dominator_tree() {
65
// Setup mappings from my Graph to Tarjan's stuff and back
66
// Note: Tarjan uses 1-based arrays
67
Tarjan* tarjan = NEW_RESOURCE_ARRAY(Tarjan, number_of_blocks() + 1);
69
// Tarjan's algorithm, almost verbatim:
71
uint dfsnum = do_DFS(tarjan, number_of_blocks());
72
if (dfsnum - 1 != number_of_blocks()) { // Check for unreachable loops!
73
// If the returned dfsnum does not match the number of blocks, then we
74
// must have some unreachable loops. These can be made at any time by
75
// IterGVN. They are cleaned up by CCP or the loop opts, but the last
76
// IterGVN can always make more that are not cleaned up. Highly unlikely
77
// except in ZKM.jar, where endless irreducible loops cause the loop opts
80
// Having found unreachable loops, we have made a bad RPO _block layout.
81
// We can re-run the above DFS pass with the correct number of blocks,
82
// and hack the Tarjan algorithm below to be robust in the presence of
83
// such dead loops (as was done for the NTarjan code farther below).
84
// Since this situation is so unlikely, instead I've decided to bail out.
86
assert(false, "unreachable loop");
87
C->record_method_not_compilable("unreachable loop");
90
_blocks._cnt = number_of_blocks();
92
// Tarjan is using 1-based arrays, so these are some initialize flags
93
tarjan[0]._size = tarjan[0]._semi = 0;
94
tarjan[0]._label = &tarjan[0];
96
for (uint i = number_of_blocks(); i >= 2; i--) { // For all vertices in DFS order
97
Tarjan *w = &tarjan[i]; // Get vertex from DFS
100
Node *whead = w->_block->head();
101
for (uint j = 1; j < whead->req(); j++) {
102
Block* b = get_block_for_node(whead->in(j));
103
Tarjan *vx = &tarjan[b->_pre_order];
104
Tarjan *u = vx->EVAL();
105
if( u->_semi < w->_semi )
109
// w is added to a bucket here, and only here.
110
// Thus w is in at most one bucket and the sum of all bucket sizes is O(n).
111
// Thus bucket can be a linked list.
112
// Thus we do not need a small integer name for each Block.
113
w->_bucket = tarjan[w->_semi]._bucket;
114
tarjan[w->_semi]._bucket = w;
116
w->_parent->LINK( w, &tarjan[0] );
119
for( Tarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) {
120
Tarjan *u = vx->EVAL();
121
vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent;
126
for (uint i = 2; i <= number_of_blocks(); i++) {
127
Tarjan *w = &tarjan[i];
128
if( w->_dom != &tarjan[w->_semi] )
129
w->_dom = w->_dom->_dom;
130
w->_dom_next = w->_dom_child = nullptr; // Initialize for building tree later
132
// No immediate dominator for the root
133
Tarjan *w = &tarjan[get_root_block()->_pre_order];
135
w->_dom_next = w->_dom_child = nullptr; // Initialize for building tree later
137
// Convert the dominator tree array into my kind of graph
138
for(uint i = 1; i <= number_of_blocks(); i++){ // For all Tarjan vertices
139
Tarjan *t = &tarjan[i]; // Handy access
140
Tarjan *tdom = t->_dom; // Handy access to immediate dominator
141
if( tdom ) { // Root has no immediate dominator
142
t->_block->_idom = tdom->_block; // Set immediate dominator
143
t->_dom_next = tdom->_dom_child; // Make me a sibling of parent's child
144
tdom->_dom_child = t; // Make me a child of my parent
146
t->_block->_idom = nullptr; // Root
148
w->setdepth(number_of_blocks() + 1); // Set depth in dominator tree
155
Block *block; // Block
156
int index; // Index of block's successor pushed on stack
157
int freq_idx; // Index of block's most frequent successor
159
Block_Descr *_stack_top;
160
Block_Descr *_stack_max;
163
uint most_frequent_successor( Block *b );
165
Block_Stack(Tarjan *tarjan, int size) : _tarjan(tarjan) {
166
_stack = NEW_RESOURCE_ARRAY(Block_Descr, size);
167
_stack_max = _stack + size;
168
_stack_top = _stack - 1; // stack is empty
170
void push(uint pre_order, Block *b) {
171
Tarjan *t = &_tarjan[pre_order]; // Fast local access
172
b->_pre_order = pre_order; // Flag as visited
173
t->_block = b; // Save actual block
174
t->_semi = pre_order; // Block to DFS map
175
t->_label = t; // DFS to vertex map
176
t->_ancestor = nullptr; // Fast LINK & EVAL setup
177
t->_child = &_tarjan[0]; // Sentenial
179
t->_bucket = nullptr;
181
t->_parent = nullptr; // first block doesn't have parent
183
// Save parent (current top block on stack) in DFS
184
t->_parent = &_tarjan[_stack_top->block->_pre_order];
186
// Now put this block on stack
188
assert(_stack_top < _stack_max, ""); // assert if stack have to grow
189
_stack_top->block = b;
190
_stack_top->index = -1;
191
// Find the index into b->succs[] array of the most frequent successor.
192
_stack_top->freq_idx = most_frequent_successor(b); // freq_idx >= 0
194
Block* pop() { Block* b = _stack_top->block; _stack_top--; return b; }
195
bool is_nonempty() { return (_stack_top >= _stack); }
196
bool last_successor() { return (_stack_top->index == _stack_top->freq_idx); }
197
Block* next_successor() {
198
int i = _stack_top->index;
200
if (i == _stack_top->freq_idx) i++;
201
if (i >= (int)(_stack_top->block->_num_succs)) {
202
i = _stack_top->freq_idx; // process most frequent successor last
204
_stack_top->index = i;
205
return _stack_top->block->_succs[ i ];
209
// Find the index into the b->succs[] array of the most frequent successor.
210
uint Block_Stack::most_frequent_successor( Block *b ) {
212
int eidx = b->end_idx();
213
Node *n = b->get_node(eidx);
214
int op = n->is_Mach() ? n->as_Mach()->ideal_Opcode() : n->Opcode();
216
case Op_CountedLoopEnd:
217
case Op_If: { // Split frequency amongst children
218
float prob = n->as_MachIf()->_prob;
219
// Is succ[0] the TRUE branch or the FALSE branch?
220
if( b->get_node(eidx+1)->Opcode() == Op_IfFalse )
222
freq_idx = prob < PROB_FAIR; // freq=1 for succ[0] < 0.5 prob
225
case Op_Catch: // Split frequency amongst children
226
for( freq_idx = 0; freq_idx < b->_num_succs; freq_idx++ )
227
if( b->get_node(eidx+1+freq_idx)->as_CatchProj()->_con == CatchProjNode::fall_through_index )
229
// Handle case of no fall-thru (e.g., check-cast MUST throw an exception)
230
if( freq_idx == b->_num_succs ) freq_idx = 0;
232
// Currently there is no support for finding out the most
233
// frequent successor for jumps, so lets just make it the first one
238
freq_idx = 0; // fall thru
247
ShouldNotReachHere();
252
// Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup
253
// 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent.
254
uint PhaseCFG::do_DFS(Tarjan *tarjan, uint rpo_counter) {
255
Block* root_block = get_root_block();
257
// Allocate stack of size number_of_blocks() + 1 to avoid frequent realloc
258
Block_Stack bstack(tarjan, number_of_blocks() + 1);
260
// Push on stack the state for the first block
261
bstack.push(pre_order, root_block);
264
while (bstack.is_nonempty()) {
265
if (!bstack.last_successor()) {
266
// Walk over all successors in pre-order (DFS).
267
Block* next_block = bstack.next_successor();
268
if (next_block->_pre_order == 0) { // Check for no-pre-order, not-visited
269
// Push on stack the state of successor
270
bstack.push(pre_order, next_block);
275
// Build a reverse post-order in the CFG _blocks array
276
Block *stack_top = bstack.pop();
277
stack_top->_rpo = --rpo_counter;
278
_blocks.map(stack_top->_rpo, stack_top);
284
void Tarjan::COMPRESS()
286
assert( _ancestor != nullptr, "" );
287
if( _ancestor->_ancestor != nullptr ) {
288
_ancestor->COMPRESS( );
289
if( _ancestor->_label->_semi < _label->_semi )
290
_label = _ancestor->_label;
291
_ancestor = _ancestor->_ancestor;
295
Tarjan *Tarjan::EVAL() {
296
if( !_ancestor ) return _label;
298
return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;
301
void Tarjan::LINK( Tarjan *w, Tarjan *tarjan0 ) {
303
while( w->_label->_semi < s->_child->_label->_semi ) {
304
if( s->_size + s->_child->_child->_size >= (s->_child->_size << 1) ) {
305
s->_child->_ancestor = s;
306
s->_child = s->_child->_child;
308
s->_child->_size = s->_size;
309
s = s->_ancestor = s->_child;
312
s->_label = w->_label;
314
if( _size < (w->_size << 1) ) {
315
Tarjan *tmp = s; s = _child; _child = tmp;
317
while( s != tarjan0 ) {
323
void Tarjan::setdepth( uint stack_size ) {
324
Tarjan **top = NEW_RESOURCE_ARRAY(Tarjan*, stack_size);
335
// Set current depth for all tarjans on this level
336
Tarjan *t = *next; // next tarjan from stack
339
t->_block->_dom_depth = depth; // Set depth in dominator tree
340
Tarjan *dom_child = t->_dom_child;
341
t = t->_dom_next; // next tarjan
342
if (dom_child != nullptr) {
343
*top = dom_child; // save child on stack
346
} while (t != nullptr);
347
} while (next < last);
348
} while (last < top);
351
// Compute dominators on the Sea of Nodes form
352
// A data structure that holds all the information needed to find dominators.
354
Node *_control; // Control node associated with this info
356
uint _semi; // Semi-dominators
357
uint _size; // Used for faster LINK and EVAL
358
NTarjan *_parent; // Parent in DFS
359
NTarjan *_label; // Used for LINK and EVAL
360
NTarjan *_ancestor; // Used for LINK and EVAL
361
NTarjan *_child; // Used for faster LINK and EVAL
362
NTarjan *_dom; // Parent in dominator tree (immediate dom)
363
NTarjan *_bucket; // Set of vertices with given semidominator
365
NTarjan *_dom_child; // Child in dominator tree
366
NTarjan *_dom_next; // Next in dominator tree
368
// Perform DFS search.
369
// Setup 'vertex' as DFS to vertex mapping.
370
// Setup 'semi' as vertex to DFS mapping.
371
// Set 'parent' to DFS parent.
372
static int DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder );
373
void setdepth( uint size, uint *dom_depth );
375
// Fast union-find work
378
void LINK( NTarjan *w, NTarjan *ntarjan0 );
380
void dump(int offset) const;
384
void remove_single_entry_region(NTarjan* t, NTarjan*& tdom, Node*& dom, PhaseIterGVN& igvn) {
386
for (DUIterator_Fast jmax, j = dom->fast_outs(jmax); j < jmax; j++) {
387
Node* use = dom->fast_out(j);
389
igvn.replace_node(use, use->in(1));
393
// Disconnect region from dominator tree
394
assert(dom->unique_ctrl_out() == t->_control, "expect a single dominated node");
397
assert(tdom->_control == dom->in(1), "dominator of region with single input should be that input");
399
igvn.replace_node(dom, dom->in(1));
400
dom = tdom->_control;
403
// Compute the dominator tree of the sea of nodes. This version walks all CFG
404
// nodes (using the is_CFG() call) and places them in a dominator tree. Thus,
405
// it needs a count of the CFG nodes for the mapping table. This is the
406
// Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
407
void PhaseIdealLoop::Dominators() {
409
// Setup mappings from my Graph to Tarjan's stuff and back
410
// Note: Tarjan uses 1-based arrays
411
NTarjan *ntarjan = NEW_RESOURCE_ARRAY(NTarjan,C->unique()+1);
412
// Initialize _control field for fast reference
414
for( i= C->unique()-1; i>=0; i-- )
415
ntarjan[i]._control = nullptr;
417
// Store the DFS order for the main loop
418
const uint fill_value = max_juint;
419
uint *dfsorder = NEW_RESOURCE_ARRAY(uint,C->unique()+1);
420
memset(dfsorder, fill_value, (C->unique()+1) * sizeof(uint));
422
// Tarjan's algorithm, almost verbatim:
425
int dfsnum = NTarjan::DFS( ntarjan, visited, this, dfsorder);
427
// Tarjan is using 1-based arrays, so these are some initialize flags
428
ntarjan[0]._size = ntarjan[0]._semi = 0;
429
ntarjan[0]._label = &ntarjan[0];
431
for( i = dfsnum-1; i>1; i-- ) { // For all nodes in reverse DFS order
432
NTarjan *w = &ntarjan[i]; // Get Node from DFS
433
assert(w->_control != nullptr,"bad DFS walk");
436
Node *whead = w->_control;
437
for( uint j=0; j < whead->req(); j++ ) { // For each predecessor
438
if( whead->in(j) == nullptr || !whead->in(j)->is_CFG() )
439
continue; // Only process control nodes
440
uint b = dfsorder[whead->in(j)->_idx];
441
if(b == fill_value) continue;
442
NTarjan *vx = &ntarjan[b];
443
NTarjan *u = vx->EVAL();
444
if( u->_semi < w->_semi )
448
// w is added to a bucket here, and only here.
449
// Thus w is in at most one bucket and the sum of all bucket sizes is O(n).
450
// Thus bucket can be a linked list.
451
w->_bucket = ntarjan[w->_semi]._bucket;
452
ntarjan[w->_semi]._bucket = w;
454
w->_parent->LINK( w, &ntarjan[0] );
457
for( NTarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) {
458
NTarjan *u = vx->EVAL();
459
vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent;
462
// Cleanup any unreachable loops now. Unreachable loops are loops that
463
// flow into the main graph (and hence into ROOT) but are not reachable
464
// from above. Such code is dead, but requires a global pass to detect
465
// it; this global pass was the 'build_loop_tree' pass run just prior.
466
if( !_verify_only && whead->is_Region() ) {
467
for( uint i = 1; i < whead->req(); i++ ) {
468
if (!has_node(whead->in(i))) {
469
// Kill dead input path
470
assert( !visited.test(whead->in(i)->_idx),
471
"input with no loop must be dead" );
472
_igvn.delete_input_of(whead, i);
473
for (DUIterator_Fast jmax, j = whead->fast_outs(jmax); j < jmax; j++) {
474
Node* p = whead->fast_out(j);
476
_igvn.delete_input_of(p, i);
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
486
for( i=2; i < dfsnum; i++ ) { // DFS order
487
NTarjan *w = &ntarjan[i];
488
assert(w->_control != nullptr,"Bad DFS walk");
489
if( w->_dom != &ntarjan[w->_semi] )
490
w->_dom = w->_dom->_dom;
491
w->_dom_next = w->_dom_child = nullptr; // Initialize for building tree later
493
// No immediate dominator for the root
494
NTarjan *w = &ntarjan[dfsorder[C->root()->_idx]];
496
w->_parent = nullptr;
497
w->_dom_next = w->_dom_child = nullptr; // Initialize for building tree later
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 != nullptr,"Bad DFS walk");
503
NTarjan *tdom = t->_dom; // Handy access to immediate dominator
504
if( tdom ) { // Root has no immediate dominator
505
Node* dom = tdom->_control;
506
// The code that removes unreachable loops above could have left a region with a single input. Remove it. Do it
507
// now that we iterate over cfg nodes for the last time (doing it earlier would have left a dead cfg node behind
508
// that code that goes over the dfs list would have had to handle).
509
if (dom != C->root() && dom->is_Region() && dom->req() == 2) {
510
remove_single_entry_region(t, tdom, dom, _igvn);
512
_idom[t->_control->_idx] = dom; // Set immediate dominator
513
t->_dom_next = tdom->_dom_child; // Make me a sibling of parent's child
514
tdom->_dom_child = t; // Make me a child of my parent
516
_idom[C->root()->_idx] = nullptr; // Root
518
w->setdepth( C->unique()+1, _dom_depth ); // Set depth in dominator tree
519
// Pick up the 'top' node as well
520
_idom [C->top()->_idx] = C->root();
521
_dom_depth[C->top()->_idx] = 1;
523
// Debug Print of Dominator tree
524
if( PrintDominators ) {
531
// Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup
532
// 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent.
533
int NTarjan::DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder) {
534
// Allocate stack of size C->live_nodes()/8 to avoid frequent realloc
535
GrowableArray <Node *> dfstack(pil->C->live_nodes() >> 3);
536
Node *b = pil->C->root();
538
dfsorder[b->_idx] = dfsnum; // Cache parent's dfsnum for a later use
541
while (dfstack.is_nonempty()) {
543
if( !visited.test_set(b->_idx) ) { // Test node and flag it as visited
544
NTarjan *w = &ntarjan[dfsnum];
545
// Only fully process control nodes
546
w->_control = b; // Save actual node
547
// Use parent's cached dfsnum to identify "Parent in DFS"
548
w->_parent = &ntarjan[dfsorder[b->_idx]];
549
dfsorder[b->_idx] = dfsnum; // Save DFS order info
550
w->_semi = dfsnum; // Node to DFS map
551
w->_label = w; // DFS to vertex map
552
w->_ancestor = nullptr; // Fast LINK & EVAL setup
553
w->_child = &ntarjan[0]; // Sentinel
555
w->_bucket = nullptr;
557
// Need DEF-USE info for this pass
558
for ( int i = b->outcnt(); i-- > 0; ) { // Put on stack backwards
559
Node* s = b->raw_out(i); // Get a use
560
// CFG nodes only and not dead stuff
561
if( s->is_CFG() && pil->has_node(s) && !visited.test(s->_idx) ) {
562
dfsorder[s->_idx] = dfsnum; // Cache parent's dfsnum for a later use
566
dfsnum++; // update after parent's dfsnum has been cached.
573
void NTarjan::COMPRESS()
575
assert( _ancestor != nullptr, "" );
576
if( _ancestor->_ancestor != nullptr ) {
577
_ancestor->COMPRESS( );
578
if( _ancestor->_label->_semi < _label->_semi )
579
_label = _ancestor->_label;
580
_ancestor = _ancestor->_ancestor;
584
NTarjan *NTarjan::EVAL() {
585
if( !_ancestor ) return _label;
587
return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;
590
void NTarjan::LINK( NTarjan *w, NTarjan *ntarjan0 ) {
592
while( w->_label->_semi < s->_child->_label->_semi ) {
593
if( s->_size + s->_child->_child->_size >= (s->_child->_size << 1) ) {
594
s->_child->_ancestor = s;
595
s->_child = s->_child->_child;
597
s->_child->_size = s->_size;
598
s = s->_ancestor = s->_child;
601
s->_label = w->_label;
603
if( _size < (w->_size << 1) ) {
604
NTarjan *tmp = s; s = _child; _child = tmp;
606
while( s != ntarjan0 ) {
612
void NTarjan::setdepth( uint stack_size, uint *dom_depth ) {
613
NTarjan **top = NEW_RESOURCE_ARRAY(NTarjan*, stack_size);
614
NTarjan **next = top;
624
// Set current depth for all tarjans on this level
625
NTarjan *t = *next; // next tarjan from stack
628
dom_depth[t->_control->_idx] = depth; // Set depth in dominator tree
629
NTarjan *dom_child = t->_dom_child;
630
t = t->_dom_next; // next tarjan
631
if (dom_child != nullptr) {
632
*top = dom_child; // save child on stack
635
} while (t != nullptr);
636
} while (next < last);
637
} while (last < top);
641
void NTarjan::dump(int offset) const {
642
// Dump the data from this node
644
for(i = offset; i >0; i--) // Use indenting for tree structure
646
tty->print("Dominator Node: ");
647
_control->dump(); // Control node for this dom node
649
for(i = offset; i >0; i--) // Use indenting for tree structure
651
tty->print("semi:%d, size:%d\n",_semi, _size);
652
for(i = offset; i >0; i--) // Use indenting for tree structure
654
tty->print("DFS Parent: ");
655
if(_parent != nullptr)
656
_parent->_control->dump(); // Parent in DFS
658
for(i = offset; i >0; i--) // Use indenting for tree structure
660
tty->print("Dom Parent: ");
662
_dom->_control->dump(); // Parent in Dominator Tree
665
// Recurse over remaining tree
666
if( _dom_child ) _dom_child->dump(offset+2); // Children in dominator tree
667
if( _dom_next ) _dom_next ->dump(offset ); // Siblings in dominator tree