jdk

1
/*
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.
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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20
 * or visit www.oracle.com if you need additional information or have any
21
 * questions.
22
 *
23
 */
24

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"
33

34
// Portions of code courtesy of Clifford Click
35

36
// A data structure that holds all the information needed to find dominators.
37
struct Tarjan {
38
  Block *_block;                // Basic block for this info
39

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
48

49
  Tarjan *_dom_child;           // Child in dominator tree
50
  Tarjan *_dom_next;            // Next in dominator tree
51

52
  // Fast union-find work
53
  void COMPRESS();
54
  Tarjan *EVAL(void);
55
  void LINK( Tarjan *w, Tarjan *tarjan0 );
56

57
  void setdepth( uint size );
58

59
};
60

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() {
64
  ResourceMark rm;
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);
68

69
  // Tarjan's algorithm, almost verbatim:
70
  // Step 1:
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
78
    // to not get run.
79
    //
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.
85
    // CNC 7/24/2001
86
    assert(false, "unreachable loop");
87
    C->record_method_not_compilable("unreachable loop");
88
    return;
89
  }
90
  _blocks._cnt = number_of_blocks();
91

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];
95

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
98

99
    // Step 2:
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 )
106
        w->_semi = u->_semi;
107
    }
108

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;
115

116
    w->_parent->LINK( w, &tarjan[0] );
117

118
    // Step 3:
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;
122
    }
123
  }
124

125
  // Step 4:
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
131
  }
132
  // No immediate dominator for the root
133
  Tarjan *w = &tarjan[get_root_block()->_pre_order];
134
  w->_dom = nullptr;
135
  w->_dom_next = w->_dom_child = nullptr;  // Initialize for building tree later
136

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
145
    } else
146
      t->_block->_idom = nullptr;  // Root
147
  }
148
  w->setdepth(number_of_blocks() + 1); // Set depth in dominator tree
149

150
}
151

152
class Block_Stack {
153
  private:
154
    struct Block_Descr {
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
158
    };
159
    Block_Descr *_stack_top;
160
    Block_Descr *_stack_max;
161
    Block_Descr *_stack;
162
    Tarjan *_tarjan;
163
    uint most_frequent_successor( Block *b );
164
  public:
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
169
    }
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
178
      t->_size = 1;
179
      t->_bucket = nullptr;
180
      if (pre_order == 1)
181
        t->_parent = nullptr;       // first block doesn't have parent
182
      else {
183
        // Save parent (current top block on stack) in DFS
184
        t->_parent = &_tarjan[_stack_top->block->_pre_order];
185
      }
186
      // Now put this block on stack
187
      ++_stack_top;
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
193
    }
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;
199
      i++;
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
203
      }
204
      _stack_top->index = i;
205
      return _stack_top->block->_succs[ i ];
206
    }
207
};
208

209
// Find the index into the b->succs[] array of the most frequent successor.
210
uint Block_Stack::most_frequent_successor( Block *b ) {
211
  uint freq_idx = 0;
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();
215
  switch( op ) {
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 )
221
      prob = 1.0f - prob;
222
    freq_idx = prob < PROB_FAIR;      // freq=1 for succ[0] < 0.5 prob
223
    break;
224
  }
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 )
228
        break;
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;
231
    break;
232
    // Currently there is no support for finding out the most
233
    // frequent successor for jumps, so lets just make it the first one
234
  case Op_Jump:
235
  case Op_Root:
236
  case Op_Goto:
237
  case Op_NeverBranch:
238
    freq_idx = 0;               // fall thru
239
    break;
240
  case Op_TailCall:
241
  case Op_TailJump:
242
  case Op_Return:
243
  case Op_Halt:
244
  case Op_Rethrow:
245
    break;
246
  default:
247
    ShouldNotReachHere();
248
  }
249
  return freq_idx;
250
}
251

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();
256
  uint pre_order = 1;
257
  // Allocate stack of size number_of_blocks() + 1 to avoid frequent realloc
258
  Block_Stack bstack(tarjan, number_of_blocks() + 1);
259

260
  // Push on stack the state for the first block
261
  bstack.push(pre_order, root_block);
262
  ++pre_order;
263

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);
271
        ++pre_order;
272
      }
273
    }
274
    else {
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);
279
    }
280
  }
281
  return pre_order;
282
}
283

284
void Tarjan::COMPRESS()
285
{
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;
292
  }
293
}
294

295
Tarjan *Tarjan::EVAL() {
296
  if( !_ancestor ) return _label;
297
  COMPRESS();
298
  return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;
299
}
300

301
void Tarjan::LINK( Tarjan *w, Tarjan *tarjan0 ) {
302
  Tarjan *s = w;
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;
307
    } else {
308
      s->_child->_size = s->_size;
309
      s = s->_ancestor = s->_child;
310
    }
311
  }
312
  s->_label = w->_label;
313
  _size += w->_size;
314
  if( _size < (w->_size << 1) ) {
315
    Tarjan *tmp = s; s = _child; _child = tmp;
316
  }
317
  while( s != tarjan0 ) {
318
    s->_ancestor = this;
319
    s = s->_child;
320
  }
321
}
322

323
void Tarjan::setdepth( uint stack_size ) {
324
  Tarjan **top  = NEW_RESOURCE_ARRAY(Tarjan*, stack_size);
325
  Tarjan **next = top;
326
  Tarjan **last;
327
  uint depth = 0;
328
  *top = this;
329
  ++top;
330
  do {
331
    // next level
332
    ++depth;
333
    last = top;
334
    do {
335
      // Set current depth for all tarjans on this level
336
      Tarjan *t = *next;     // next tarjan from stack
337
      ++next;
338
      do {
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
344
          ++top;
345
        }
346
      } while (t != nullptr);
347
    } while (next < last);
348
  } while (last < top);
349
}
350

351
// Compute dominators on the Sea of Nodes form
352
// A data structure that holds all the information needed to find dominators.
353
struct NTarjan {
354
  Node *_control;               // Control node associated with this info
355

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
364

365
  NTarjan *_dom_child;          // Child in dominator tree
366
  NTarjan *_dom_next;           // Next in dominator tree
367

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 );
374

375
  // Fast union-find work
376
  void COMPRESS();
377
  NTarjan *EVAL(void);
378
  void LINK( NTarjan *w, NTarjan *ntarjan0 );
379
#ifndef PRODUCT
380
  void dump(int offset) const;
381
#endif
382
};
383

384
void remove_single_entry_region(NTarjan* t, NTarjan*& tdom, Node*& dom, PhaseIterGVN& igvn) {
385
  // remove phis:
386
  for (DUIterator_Fast jmax, j = dom->fast_outs(jmax); j < jmax; j++) {
387
    Node* use = dom->fast_out(j);
388
    if (use->is_Phi()) {
389
      igvn.replace_node(use, use->in(1));
390
      --j; --jmax;
391
    }
392
  }
393
  // Disconnect region from dominator tree
394
  assert(dom->unique_ctrl_out() == t->_control, "expect a single dominated node");
395
  tdom = tdom->_dom;
396
  t->_dom = tdom;
397
  assert(tdom->_control == dom->in(1), "dominator of region with single input should be that input");
398
  // and remove it
399
  igvn.replace_node(dom, dom->in(1));
400
  dom = tdom->_control;
401
}
402

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() {
408
  ResourceMark rm;
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
413
  int i;
414
  for( i= C->unique()-1; i>=0; i-- )
415
    ntarjan[i]._control = nullptr;
416

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));
421

422
  // Tarjan's algorithm, almost verbatim:
423
  // Step 1:
424
  VectorSet visited;
425
  int dfsnum = NTarjan::DFS( ntarjan, visited, this, dfsorder);
426

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];
430

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");
434

435
    // Step 2:
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 )
445
        w->_semi = u->_semi;
446
    }
447

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;
453

454
    w->_parent->LINK( w, &ntarjan[0] );
455

456
    // Step 3:
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;
460
    }
461

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);
475
            if( p->is_Phi() ) {
476
              _igvn.delete_input_of(p, i);
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 != 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
492
  }
493
  // No immediate dominator for the root
494
  NTarjan *w = &ntarjan[dfsorder[C->root()->_idx]];
495
  w->_dom = nullptr;
496
  w->_parent = nullptr;
497
  w->_dom_next = w->_dom_child = nullptr;  // 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 != 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);
511
      }
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
515
    } else
516
      _idom[C->root()->_idx] = nullptr; // Root
517
  }
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;
522

523
  // Debug Print of Dominator tree
524
  if( PrintDominators ) {
525
#ifndef PRODUCT
526
    w->dump(0);
527
#endif
528
  }
529
}
530

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();
537
  int dfsnum = 1;
538
  dfsorder[b->_idx] = dfsnum; // Cache parent's dfsnum for a later use
539
  dfstack.push(b);
540

541
  while (dfstack.is_nonempty()) {
542
    b = dfstack.pop();
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
554
      w->_size = 1;
555
      w->_bucket = nullptr;
556

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
563
          dfstack.push(s);
564
        }
565
      }
566
      dfsnum++;  // update after parent's dfsnum has been cached.
567
    }
568
  }
569

570
  return dfsnum;
571
}
572

573
void NTarjan::COMPRESS()
574
{
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;
581
  }
582
}
583

584
NTarjan *NTarjan::EVAL() {
585
  if( !_ancestor ) return _label;
586
  COMPRESS();
587
  return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;
588
}
589

590
void NTarjan::LINK( NTarjan *w, NTarjan *ntarjan0 ) {
591
  NTarjan *s = w;
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;
596
    } else {
597
      s->_child->_size = s->_size;
598
      s = s->_ancestor = s->_child;
599
    }
600
  }
601
  s->_label = w->_label;
602
  _size += w->_size;
603
  if( _size < (w->_size << 1) ) {
604
    NTarjan *tmp = s; s = _child; _child = tmp;
605
  }
606
  while( s != ntarjan0 ) {
607
    s->_ancestor = this;
608
    s = s->_child;
609
  }
610
}
611

612
void NTarjan::setdepth( uint stack_size, uint *dom_depth ) {
613
  NTarjan **top  = NEW_RESOURCE_ARRAY(NTarjan*, stack_size);
614
  NTarjan **next = top;
615
  NTarjan **last;
616
  uint depth = 0;
617
  *top = this;
618
  ++top;
619
  do {
620
    // next level
621
    ++depth;
622
    last = top;
623
    do {
624
      // Set current depth for all tarjans on this level
625
      NTarjan *t = *next;    // next tarjan from stack
626
      ++next;
627
      do {
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
633
          ++top;
634
        }
635
      } while (t != nullptr);
636
    } while (next < last);
637
  } while (last < top);
638
}
639

640
#ifndef PRODUCT
641
void NTarjan::dump(int offset) const {
642
  // Dump the data from this node
643
  int i;
644
  for(i = offset; i >0; i--)  // Use indenting for tree structure
645
    tty->print("  ");
646
  tty->print("Dominator Node: ");
647
  _control->dump();               // Control node for this dom node
648
  tty->print("\n");
649
  for(i = offset; i >0; i--)      // Use indenting for tree structure
650
    tty->print("  ");
651
  tty->print("semi:%d, size:%d\n",_semi, _size);
652
  for(i = offset; i >0; i--)      // Use indenting for tree structure
653
    tty->print("  ");
654
  tty->print("DFS Parent: ");
655
  if(_parent != nullptr)
656
    _parent->_control->dump();    // Parent in DFS
657
  tty->print("\n");
658
  for(i = offset; i >0; i--)      // Use indenting for tree structure
659
    tty->print("  ");
660
  tty->print("Dom Parent: ");
661
  if(_dom != nullptr)
662
    _dom->_control->dump();       // Parent in Dominator Tree
663
  tty->print("\n");
664

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
668

669
}
670
#endif
671