< prev index next >

src/hotspot/share/opto/loopnode.cpp

Print this page




  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "ci/ciMethodData.hpp"
  27 #include "compiler/compileLog.hpp"
  28 #include "gc/shared/barrierSet.hpp"
  29 #include "gc/shared/c2/barrierSetC2.hpp"
  30 #include "libadt/vectset.hpp"
  31 #include "memory/allocation.inline.hpp"
  32 #include "memory/resourceArea.hpp"
  33 #include "opto/addnode.hpp"
  34 #include "opto/callnode.hpp"
  35 #include "opto/connode.hpp"
  36 #include "opto/convertnode.hpp"
  37 #include "opto/divnode.hpp"
  38 #include "opto/idealGraphPrinter.hpp"
  39 #include "opto/loopnode.hpp"
  40 #include "opto/mulnode.hpp"
  41 #include "opto/rootnode.hpp"
  42 #include "opto/superword.hpp"




  43 
  44 //=============================================================================
  45 //------------------------------is_loop_iv-------------------------------------
  46 // Determine if a node is Counted loop induction variable.
  47 // The method is declared in node.hpp.
  48 const Node* Node::is_loop_iv() const {
  49   if (this->is_Phi() && !this->as_Phi()->is_copy() &&
  50       this->as_Phi()->region()->is_CountedLoop() &&
  51       this->as_Phi()->region()->as_CountedLoop()->phi() == this) {
  52     return this;
  53   } else {
  54     return NULL;
  55   }
  56 }
  57 
  58 //=============================================================================
  59 //------------------------------dump_spec--------------------------------------
  60 // Dump special per-node info
  61 #ifndef PRODUCT
  62 void LoopNode::dump_spec(outputStream *st) const {


 979           continue;
 980         }
 981         wq.clear();
 982         wq.push(u);
 983         bool found_sfpt = false;
 984         for (uint next = 0; next < wq.size() && !found_sfpt; next++) {
 985           Node *n = wq.at(next);
 986           for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax && !found_sfpt; i++) {
 987             Node* u = n->fast_out(i);
 988             if (u == sfpt) {
 989               found_sfpt = true;
 990             }
 991             if (!u->is_CFG()) {
 992               wq.push(u);
 993             }
 994           }
 995         }
 996         assert(found_sfpt, "no node in loop that's not input to safepoint");
 997       }
 998     }
 999     CountedLoopEndNode* cle = inner_out->in(0)->as_CountedLoopEnd();
1000     assert(cle == inner->loopexit_or_null(), "mismatch");
1001     bool has_skeleton = outer_le->in(1)->bottom_type()->singleton() && outer_le->in(1)->bottom_type()->is_int()->get_con() == 0;
1002     if (has_skeleton) {


1003       assert(expect_skeleton == 1 || expect_skeleton == -1, "unexpected skeleton node");
1004       assert(outer->outcnt() == 2, "only phis");
1005     } else {
1006       assert(expect_skeleton == 0 || expect_skeleton == -1, "no skeleton node?");
1007       uint phis = 0;
1008       for (DUIterator_Fast imax, i = inner->fast_outs(imax); i < imax; i++) {
1009         Node* u = inner->fast_out(i);
1010         if (u->is_Phi()) {
1011           phis++;
1012         }
1013       }
1014       for (DUIterator_Fast imax, i = outer->fast_outs(imax); i < imax; i++) {
1015         Node* u = outer->fast_out(i);
1016         assert(u == outer || u == inner || u->is_Phi(), "nothing between inner and outer loop");
1017       }
1018       uint stores = 0;
1019       for (DUIterator_Fast imax, i = inner_out->fast_outs(imax); i < imax; i++) {
1020         Node* u = inner_out->fast_out(i);
1021         if (u->is_Store()) {
1022           stores++;


1784           // Go ahead and clean out old edges from old phi
1785           old_phi->del_req(i);
1786         }
1787       }
1788       // Search for CSE's here, because ZKM.jar does a lot of
1789       // loop hackery and we need to be a little incremental
1790       // with the CSE to avoid O(N^2) node blow-up.
1791       Node *p2 = igvn.hash_find_insert(p); // Look for a CSE
1792       if( p2 ) {                // Found CSE
1793         p->destruct();          // Recover useless new node
1794         p = p2;                 // Use old node
1795       } else {
1796         igvn.register_new_node_with_optimizer(p, old_phi);
1797       }
1798       // Make old Phi refer to new Phi.
1799       old_phi->add_req(p);
1800       // Check for the special case of making the old phi useless and
1801       // disappear it.  In JavaGrande I have a case where this useless
1802       // Phi is the loop limit and prevents recognizing a CountedLoop
1803       // which in turn prevents removing an empty loop.
1804       Node *id_old_phi = old_phi->Identity( &igvn );
1805       if( id_old_phi != old_phi ) { // Found a simple identity?
1806         // Note that I cannot call 'replace_node' here, because
1807         // that will yank the edge from old_phi to the Region and
1808         // I'm mid-iteration over the Region's uses.
1809         for (DUIterator_Last imin, i = old_phi->last_outs(imin); i >= imin; ) {
1810           Node* use = old_phi->last_out(i);
1811           igvn.rehash_node_delayed(use);
1812           uint uses_found = 0;
1813           for (uint j = 0; j < use->len(); j++) {
1814             if (use->in(j) == old_phi) {
1815               if (j < use->req()) use->set_req (j, id_old_phi);
1816               else                use->set_prec(j, id_old_phi);
1817               uses_found++;
1818             }
1819           }
1820           i -= uses_found;    // we deleted 1 or more copies of this edge
1821         }
1822       }
1823       igvn._worklist.push(old_phi);
1824     }


2696         }
2697         if (n2->in(0) != c2) {
2698           _igvn.hash_delete(n2);
2699           n2->set_req(0, c2);
2700           _igvn.hash_insert(n2);
2701           _igvn._worklist.push(n2);
2702           progress = true;
2703         }
2704       }
2705     }
2706   }
2707 
2708   return progress;
2709 }
2710 
2711 
2712 //=============================================================================
2713 //----------------------------build_and_optimize-------------------------------
2714 // Create a PhaseLoop.  Build the ideal Loop tree.  Map each Ideal Node to
2715 // its corresponding LoopNode.  If 'optimize' is true, do some loop cleanups.
2716 void PhaseIdealLoop::build_and_optimize(bool do_split_ifs, bool skip_loop_opts, bool last_round) {





2717   ResourceMark rm;
2718 
2719   int old_progress = C->major_progress();
2720   uint orig_worklist_size = _igvn._worklist.size();
2721 
2722   // Reset major-progress flag for the driver's heuristics
2723   C->clear_major_progress();
2724 
2725 #ifndef PRODUCT
2726   // Capture for later assert
2727   uint unique = C->unique();
2728   _loop_invokes++;
2729   _loop_work += unique;
2730 #endif
2731 
2732   // True if the method has at least 1 irreducible loop
2733   _has_irreducible_loops = false;
2734 
2735   _created_loop_node = false;
2736 


2760   build_loop_tree();
2761   // Check for bailout, and return
2762   if (C->failing()) {
2763     return;
2764   }
2765 
2766   // No loops after all
2767   if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
2768 
2769   // There should always be an outer loop containing the Root and Return nodes.
2770   // If not, we have a degenerate empty program.  Bail out in this case.
2771   if (!has_node(C->root())) {
2772     if (!_verify_only) {
2773       C->clear_major_progress();
2774       C->record_method_not_compilable("empty program detected during loop optimization");
2775     }
2776     return;
2777   }
2778 
2779   // Nothing to do, so get out
2780   bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !_verify_me && !_verify_only;
2781   bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
2782   if (stop_early && !do_expensive_nodes) {
2783     _igvn.optimize();           // Cleanup NeverBranches
2784     return;
2785   }
2786 
2787   // Set loop nesting depth
2788   _ltree_root->set_nest( 0 );
2789 
2790   // Split shared headers and insert loop landing pads.
2791   // Do not bother doing this on the Root loop of course.
2792   if( !_verify_me && !_verify_only && _ltree_root->_child ) {
2793     C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
2794     if( _ltree_root->_child->beautify_loops( this ) ) {
2795       // Re-build loop tree!
2796       _ltree_root->_child = NULL;
2797       _nodes.clear();
2798       reallocate_preorders();
2799       build_loop_tree();
2800       // Check for bailout, and return


2839 
2840   // Walk the DATA nodes and place into loops.  Find earliest control
2841   // node.  For CFG nodes, the _nodes array starts out and remains
2842   // holding the associated IdealLoopTree pointer.  For DATA nodes, the
2843   // _nodes array holds the earliest legal controlling CFG node.
2844 
2845   // Allocate stack with enough space to avoid frequent realloc
2846   int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
2847   Node_Stack nstack( a, stack_size );
2848 
2849   visited.Clear();
2850   Node_List worklist(a);
2851   // Don't need C->root() on worklist since
2852   // it will be processed among C->top() inputs
2853   worklist.push( C->top() );
2854   visited.set( C->top()->_idx ); // Set C->top() as visited now
2855   build_loop_early( visited, worklist, nstack );
2856 
2857   // Given early legal placement, try finding counted loops.  This placement
2858   // is good enough to discover most loop invariants.
2859   if( !_verify_me && !_verify_only )
2860     _ltree_root->counted_loop( this );

2861 
2862   // Find latest loop placement.  Find ideal loop placement.
2863   visited.Clear();
2864   init_dom_lca_tags();
2865   // Need C->root() on worklist when processing outs
2866   worklist.push( C->root() );
2867   NOT_PRODUCT( C->verify_graph_edges(); )
2868   worklist.push( C->top() );
2869   build_loop_late( visited, worklist, nstack );
2870 
2871   if (_verify_only) {
2872     // restore major progress flag
2873     for (int i = 0; i < old_progress; i++)
2874       C->set_major_progress();
2875     assert(C->unique() == unique, "verification mode made Nodes? ? ?");
2876     assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
2877     return;
2878   }
2879 
2880   // clear out the dead code after build_loop_late
2881   while (_deadlist.size()) {
2882     _igvn.remove_globally_dead_node(_deadlist.pop());
2883   }
2884 
2885   if (stop_early) {
2886     assert(do_expensive_nodes, "why are we here?");
2887     if (process_expensive_nodes()) {
2888       // If we made some progress when processing expensive nodes then
2889       // the IGVN may modify the graph in a way that will allow us to


2911   if(TraceLoopOpts && C->has_loops()) {
2912     _ltree_root->dump();
2913   }
2914 #endif
2915 
2916   if (skip_loop_opts) {
2917     // restore major progress flag
2918     for (int i = 0; i < old_progress; i++) {
2919       C->set_major_progress();
2920     }
2921 
2922     // Cleanup any modified bits
2923     _igvn.optimize();
2924 
2925     if (C->log() != NULL) {
2926       log_loop_tree(_ltree_root, _ltree_root, C->log());
2927     }
2928     return;
2929   }
2930 










2931   if (ReassociateInvariants) {
2932     // Reassociate invariants and prep for split_thru_phi
2933     for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2934       IdealLoopTree* lpt = iter.current();
2935       bool is_counted = lpt->is_counted();
2936       if (!is_counted || !lpt->is_inner()) continue;
2937 
2938       // check for vectorized loops, any reassociation of invariants was already done
2939       if (is_counted && lpt->_head->as_CountedLoop()->do_unroll_only()) continue;
2940 
2941       lpt->reassociate_invariants(this);
2942 
2943       // Because RCE opportunities can be masked by split_thru_phi,
2944       // look for RCE candidates and inhibit split_thru_phi
2945       // on just their loop-phi's for this pass of loop opts
2946       if (SplitIfBlocks && do_split_ifs) {
2947         if (lpt->policy_range_check(this)) {
2948           lpt->_rce_candidate = 1; // = true
2949         }
2950       }
2951     }
2952   }
2953 
2954   // Check for aggressive application of split-if and other transforms
2955   // that require basic-block info (like cloning through Phi's)
2956   if( SplitIfBlocks && do_split_ifs ) {
2957     visited.Clear();
2958     split_if_with_blocks( visited, nstack, last_round );
2959     NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); );
2960     if (last_round) {
2961       C->set_major_progress();
2962     }
2963   }
2964 
2965   if (!C->major_progress() && do_expensive_nodes && process_expensive_nodes()) {
2966     C->set_major_progress();
2967   }
2968 
2969   // Perform loop predication before iteration splitting
2970   if (C->has_loops() && !C->major_progress() && (C->predicate_count() > 0)) {
2971     _ltree_root->_child->loop_predication(this);
2972   }
2973 
2974   if (OptimizeFill && UseLoopPredicate && C->has_loops() && !C->major_progress()) {
2975     if (do_intrinsify_fill()) {
2976       C->set_major_progress();
2977     }
2978   }
2979 
2980   // Perform iteration-splitting on inner loops.  Split iterations to avoid


3941     compute_lca_of_uses(n, early, true);
3942   }
3943 #endif
3944 
3945   // if this is a load, check for anti-dependent stores
3946   // We use a conservative algorithm to identify potential interfering
3947   // instructions and for rescheduling the load.  The users of the memory
3948   // input of this load are examined.  Any use which is not a load and is
3949   // dominated by early is considered a potentially interfering store.
3950   // This can produce false positives.
3951   if (n->is_Load() && LCA != early) {
3952     Node_List worklist;
3953 
3954     Node *mem = n->in(MemNode::Memory);
3955     for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
3956       Node* s = mem->fast_out(i);
3957       worklist.push(s);
3958     }
3959     while(worklist.size() != 0 && LCA != early) {
3960       Node* s = worklist.pop();
3961       if (s->is_Load() || s->Opcode() == Op_SafePoint) {

3962         continue;
3963       } else if (s->is_MergeMem()) {
3964         for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) {
3965           Node* s1 = s->fast_out(i);
3966           worklist.push(s1);
3967         }
3968       } else {
3969         Node *sctrl = has_ctrl(s) ? get_ctrl(s) : s->in(0);
3970         assert(sctrl != NULL || s->outcnt() == 0, "must have control");
3971         if (sctrl != NULL && !sctrl->is_top() && is_dominator(early, sctrl)) {
3972           LCA = dom_lca_for_get_late_ctrl(LCA, sctrl, n);
3973         }
3974       }
3975     }
3976   }
3977 
3978   assert(LCA == find_non_split_ctrl(LCA), "unexpected late control");
3979   return LCA;
3980 }
3981 


4068 }
4069 
4070 //------------------------------clear_dom_lca_tags------------------------------
4071 // Tag could be a node's integer index, 32bits instead of 64bits in some cases
4072 // Intended use does not involve any growth for the array, so it could
4073 // be of fixed size.
4074 void PhaseIdealLoop::clear_dom_lca_tags() {
4075   uint limit = C->unique() + 1;
4076   _dom_lca_tags.map( limit, NULL );
4077   _dom_lca_tags.clear();
4078 #ifdef ASSERT
4079   for( uint i = 0; i < limit; ++i ) {
4080     assert(_dom_lca_tags[i] == NULL, "Must be distinct from each node pointer");
4081   }
4082 #endif // ASSERT
4083 }
4084 
4085 //------------------------------build_loop_late--------------------------------
4086 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
4087 // Second pass finds latest legal placement, and ideal loop placement.
4088 void PhaseIdealLoop::build_loop_late( VectorSet &visited, Node_List &worklist, Node_Stack &nstack ) {
4089   while (worklist.size() != 0) {
4090     Node *n = worklist.pop();
4091     // Only visit once
4092     if (visited.test_set(n->_idx)) continue;
4093     uint cnt = n->outcnt();
4094     uint   i = 0;
4095     while (true) {
4096       assert( _nodes[n->_idx], "no dead nodes" );
4097       // Visit all children
4098       if (i < cnt) {
4099         Node* use = n->raw_out(i);
4100         ++i;
4101         // Check for dead uses.  Aggressively prune such junk.  It might be
4102         // dead in the global sense, but still have local uses so I cannot
4103         // easily call 'remove_dead_node'.
4104         if( _nodes[use->_idx] != NULL || use->is_top() ) { // Not dead?
4105           // Due to cycles, we might not hit the same fixed point in the verify
4106           // pass as we do in the regular pass.  Instead, visit such phis as
4107           // simple uses of the loop head.
4108           if( use->in(0) && (use->is_CFG() || use->is_Phi()) ) {
4109             if( !visited.test(use->_idx) )
4110               worklist.push(use);
4111           } else if( !visited.test_set(use->_idx) ) {
4112             nstack.push(n, i); // Save parent and next use's index.
4113             n   = use;         // Process all children of current use.
4114             cnt = use->outcnt();
4115             i   = 0;
4116           }
4117         } else {
4118           // Do not visit around the backedge of loops via data edges.
4119           // push dead code onto a worklist
4120           _deadlist.push(use);
4121         }
4122       } else {
4123         // All of n's children have been processed, complete post-processing.
4124         build_loop_late_post(n);
4125         if (nstack.is_empty()) {
4126           // Finished all nodes on stack.
4127           // Process next node on the worklist.
4128           break;
4129         }
4130         // Get saved parent node and next use's index. Visit the rest of uses.
4131         n   = nstack.node();
4132         cnt = n->outcnt();
4133         i   = nstack.index();
4134         nstack.pop();
4135       }
4136     }
4137   }
4138 }
4139 
4140 // Verify that no data node is schedules in the outer loop of a strip
4141 // mined loop.
4142 void PhaseIdealLoop::verify_strip_mined_scheduling(Node *n, Node* least) {
4143 #ifdef ASSERT
4144   if (get_loop(least)->_nest == 0) {


4155       Node *m = wq.at(i);
4156       for (uint i = 1; i < m->req(); i++) {
4157         Node* nn = m->in(i);
4158         if (nn == n) {
4159           return;
4160         }
4161         if (nn != NULL && has_ctrl(nn) && get_loop(get_ctrl(nn)) == loop) {
4162           wq.push(nn);
4163         }
4164       }
4165     }
4166     ShouldNotReachHere();
4167   }
4168 #endif
4169 }
4170 
4171 
4172 //------------------------------build_loop_late_post---------------------------
4173 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
4174 // Second pass finds latest legal placement, and ideal loop placement.
4175 void PhaseIdealLoop::build_loop_late_post( Node *n ) {
4176 
4177   if (n->req() == 2 && (n->Opcode() == Op_ConvI2L || n->Opcode() == Op_CastII) && !C->major_progress() && !_verify_only) {
4178     _igvn._worklist.push(n);  // Maybe we'll normalize it, if no more loops.
4179   }
4180 
4181 #ifdef ASSERT
4182   if (_verify_only && !n->is_CFG()) {
4183     // Check def-use domination.
4184     compute_lca_of_uses(n, get_ctrl(n), true /* verify */);
4185   }
4186 #endif
4187 
4188   // CFG and pinned nodes already handled
4189   if( n->in(0) ) {
4190     if( n->in(0)->is_top() ) return; // Dead?
4191 
4192     // We'd like +VerifyLoopOptimizations to not believe that Mod's/Loads
4193     // _must_ be pinned (they have to observe their control edge of course).
4194     // Unlike Stores (which modify an unallocable resource, the memory
4195     // state), Mods/Loads can float around.  So free them up.


4311     }
4312   }
4313 
4314 #ifdef ASSERT
4315   // If verifying, verify that 'verify_me' has a legal location
4316   // and choose it as our location.
4317   if( _verify_me ) {
4318     Node *v_ctrl = _verify_me->get_ctrl_no_update(n);
4319     Node *legal = LCA;
4320     while( early != legal ) {   // While not at earliest legal
4321       if( legal == v_ctrl ) break;  // Check for prior good location
4322       legal = idom(legal)      ;// Bump up the IDOM tree
4323     }
4324     // Check for prior good location
4325     if( legal == v_ctrl ) least = legal; // Keep prior if found
4326   }
4327 #endif
4328 
4329   // Assign discovered "here or above" point
4330   least = find_non_split_ctrl(least);
4331   verify_strip_mined_scheduling(n, least);


4332   set_ctrl(n, least);
4333 
4334   // Collect inner loop bodies
4335   IdealLoopTree *chosen_loop = get_loop(least);
4336   if( !chosen_loop->_child )   // Inner loop?
4337     chosen_loop->_body.push(n);// Collect inner loops
4338 }
4339 
4340 #ifdef ASSERT
4341 void PhaseIdealLoop::dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA) {
4342   tty->print_cr("%s", msg);
4343   tty->print("n: "); n->dump();
4344   tty->print("early(n): "); early->dump();
4345   if (n->in(0) != NULL  && !n->in(0)->is_top() &&
4346       n->in(0) != early && !n->in(0)->is_Root()) {
4347     tty->print("n->in(0): "); n->in(0)->dump();
4348   }
4349   for (uint i = 1; i < n->req(); i++) {
4350     Node* in1 = n->in(i);
4351     if (in1 != NULL && in1 != n && !in1->is_top()) {


4473     }
4474     // Dump nodes it controls
4475     for( uint k = 0; k < _nodes.Size(); k++ ) {
4476       // (k < C->unique() && get_ctrl(find(k)) == n)
4477       if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
4478         Node *m = C->root()->find(k);
4479         if( m && m->outcnt() > 0 ) {
4480           if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
4481             tty->print_cr("*** BROKEN CTRL ACCESSOR!  _nodes[k] is %p, ctrl is %p",
4482                           _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
4483           }
4484           for( uint j = 0; j < loop->_nest; j++ )
4485             tty->print("  ");
4486           tty->print(" ");
4487           m->dump();
4488         }
4489       }
4490     }
4491   }
4492 }

4493 
4494 // Collect a R-P-O for the whole CFG.
4495 // Result list is in post-order (scan backwards for RPO)
4496 void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const {
4497   stk.push(start, 0);
4498   visited.set(start->_idx);
4499 
4500   while (stk.is_nonempty()) {
4501     Node* m   = stk.node();
4502     uint  idx = stk.index();
4503     if (idx < m->outcnt()) {
4504       stk.set_index(idx + 1);
4505       Node* n = m->raw_out(idx);
4506       if (n->is_CFG() && !visited.test_set(n->_idx)) {
4507         stk.push(n, 0);
4508       }
4509     } else {
4510       rpo_list.push(m);
4511       stk.pop();
4512     }
4513   }
4514 }
4515 #endif
4516 
4517 
4518 //=============================================================================
4519 //------------------------------LoopTreeIterator-----------------------------------
4520 
4521 // Advance to next loop tree using a preorder, left-to-right traversal.
4522 void LoopTreeIterator::next() {
4523   assert(!done(), "must not be done.");
4524   if (_curnt->_child != NULL) {
4525     _curnt = _curnt->_child;
4526   } else if (_curnt->_next != NULL) {
4527     _curnt = _curnt->_next;
4528   } else {
4529     while (_curnt != _root && _curnt->_next == NULL) {
4530       _curnt = _curnt->_parent;
4531     }
4532     if (_curnt == _root) {
4533       _curnt = NULL;
4534       assert(done(), "must be done.");
4535     } else {


  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "ci/ciMethodData.hpp"
  27 #include "compiler/compileLog.hpp"
  28 #include "gc/shared/barrierSet.hpp"
  29 #include "gc/shared/c2/barrierSetC2.hpp"
  30 #include "libadt/vectset.hpp"
  31 #include "memory/allocation.inline.hpp"
  32 #include "memory/resourceArea.hpp"
  33 #include "opto/addnode.hpp"
  34 #include "opto/callnode.hpp"
  35 #include "opto/connode.hpp"
  36 #include "opto/convertnode.hpp"
  37 #include "opto/divnode.hpp"
  38 #include "opto/idealGraphPrinter.hpp"
  39 #include "opto/loopnode.hpp"
  40 #include "opto/mulnode.hpp"
  41 #include "opto/rootnode.hpp"
  42 #include "opto/superword.hpp"
  43 #include "utilities/macros.hpp"
  44 #if INCLUDE_SHENANDOAHGC
  45 #include "gc/shenandoah/c2/shenandoahBarrierSetC2.hpp"
  46 #endif
  47 
  48 //=============================================================================
  49 //------------------------------is_loop_iv-------------------------------------
  50 // Determine if a node is Counted loop induction variable.
  51 // The method is declared in node.hpp.
  52 const Node* Node::is_loop_iv() const {
  53   if (this->is_Phi() && !this->as_Phi()->is_copy() &&
  54       this->as_Phi()->region()->is_CountedLoop() &&
  55       this->as_Phi()->region()->as_CountedLoop()->phi() == this) {
  56     return this;
  57   } else {
  58     return NULL;
  59   }
  60 }
  61 
  62 //=============================================================================
  63 //------------------------------dump_spec--------------------------------------
  64 // Dump special per-node info
  65 #ifndef PRODUCT
  66 void LoopNode::dump_spec(outputStream *st) const {


 983           continue;
 984         }
 985         wq.clear();
 986         wq.push(u);
 987         bool found_sfpt = false;
 988         for (uint next = 0; next < wq.size() && !found_sfpt; next++) {
 989           Node *n = wq.at(next);
 990           for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax && !found_sfpt; i++) {
 991             Node* u = n->fast_out(i);
 992             if (u == sfpt) {
 993               found_sfpt = true;
 994             }
 995             if (!u->is_CFG()) {
 996               wq.push(u);
 997             }
 998           }
 999         }
1000         assert(found_sfpt, "no node in loop that's not input to safepoint");
1001       }
1002     }


1003     bool has_skeleton = outer_le->in(1)->bottom_type()->singleton() && outer_le->in(1)->bottom_type()->is_int()->get_con() == 0;
1004     if (has_skeleton) {
1005       CountedLoopEndNode* cle = inner_out->in(0)->as_CountedLoopEnd();
1006       assert(cle == inner->loopexit_or_null(), "mismatch");
1007       assert(expect_skeleton == 1 || expect_skeleton == -1, "unexpected skeleton node");
1008       assert(outer->outcnt() == 2, "only phis");
1009     } else {
1010       assert(expect_skeleton == 0 || expect_skeleton == -1, "no skeleton node?");
1011       uint phis = 0;
1012       for (DUIterator_Fast imax, i = inner->fast_outs(imax); i < imax; i++) {
1013         Node* u = inner->fast_out(i);
1014         if (u->is_Phi()) {
1015           phis++;
1016         }
1017       }
1018       for (DUIterator_Fast imax, i = outer->fast_outs(imax); i < imax; i++) {
1019         Node* u = outer->fast_out(i);
1020         assert(u == outer || u == inner || u->is_Phi(), "nothing between inner and outer loop");
1021       }
1022       uint stores = 0;
1023       for (DUIterator_Fast imax, i = inner_out->fast_outs(imax); i < imax; i++) {
1024         Node* u = inner_out->fast_out(i);
1025         if (u->is_Store()) {
1026           stores++;


1788           // Go ahead and clean out old edges from old phi
1789           old_phi->del_req(i);
1790         }
1791       }
1792       // Search for CSE's here, because ZKM.jar does a lot of
1793       // loop hackery and we need to be a little incremental
1794       // with the CSE to avoid O(N^2) node blow-up.
1795       Node *p2 = igvn.hash_find_insert(p); // Look for a CSE
1796       if( p2 ) {                // Found CSE
1797         p->destruct();          // Recover useless new node
1798         p = p2;                 // Use old node
1799       } else {
1800         igvn.register_new_node_with_optimizer(p, old_phi);
1801       }
1802       // Make old Phi refer to new Phi.
1803       old_phi->add_req(p);
1804       // Check for the special case of making the old phi useless and
1805       // disappear it.  In JavaGrande I have a case where this useless
1806       // Phi is the loop limit and prevents recognizing a CountedLoop
1807       // which in turn prevents removing an empty loop.
1808       Node *id_old_phi = igvn.apply_identity(old_phi);
1809       if( id_old_phi != old_phi ) { // Found a simple identity?
1810         // Note that I cannot call 'replace_node' here, because
1811         // that will yank the edge from old_phi to the Region and
1812         // I'm mid-iteration over the Region's uses.
1813         for (DUIterator_Last imin, i = old_phi->last_outs(imin); i >= imin; ) {
1814           Node* use = old_phi->last_out(i);
1815           igvn.rehash_node_delayed(use);
1816           uint uses_found = 0;
1817           for (uint j = 0; j < use->len(); j++) {
1818             if (use->in(j) == old_phi) {
1819               if (j < use->req()) use->set_req (j, id_old_phi);
1820               else                use->set_prec(j, id_old_phi);
1821               uses_found++;
1822             }
1823           }
1824           i -= uses_found;    // we deleted 1 or more copies of this edge
1825         }
1826       }
1827       igvn._worklist.push(old_phi);
1828     }


2700         }
2701         if (n2->in(0) != c2) {
2702           _igvn.hash_delete(n2);
2703           n2->set_req(0, c2);
2704           _igvn.hash_insert(n2);
2705           _igvn._worklist.push(n2);
2706           progress = true;
2707         }
2708       }
2709     }
2710   }
2711 
2712   return progress;
2713 }
2714 
2715 
2716 //=============================================================================
2717 //----------------------------build_and_optimize-------------------------------
2718 // Create a PhaseLoop.  Build the ideal Loop tree.  Map each Ideal Node to
2719 // its corresponding LoopNode.  If 'optimize' is true, do some loop cleanups.
2720 void PhaseIdealLoop::build_and_optimize(LoopOptsMode mode) {
2721   bool do_split_ifs = (mode == LoopOptsDefault || mode == LoopOptsZgcLastRound);
2722   bool skip_loop_opts = (mode == LoopOptsNone) ;
2723   bool shenandoah_opts = (mode == LoopOptsShenandoahExpand ||
2724                           mode == LoopOptsShenandoahPostExpand);
2725 
2726   ResourceMark rm;
2727 
2728   int old_progress = C->major_progress();
2729   uint orig_worklist_size = _igvn._worklist.size();
2730 
2731   // Reset major-progress flag for the driver's heuristics
2732   C->clear_major_progress();
2733 
2734 #ifndef PRODUCT
2735   // Capture for later assert
2736   uint unique = C->unique();
2737   _loop_invokes++;
2738   _loop_work += unique;
2739 #endif
2740 
2741   // True if the method has at least 1 irreducible loop
2742   _has_irreducible_loops = false;
2743 
2744   _created_loop_node = false;
2745 


2769   build_loop_tree();
2770   // Check for bailout, and return
2771   if (C->failing()) {
2772     return;
2773   }
2774 
2775   // No loops after all
2776   if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
2777 
2778   // There should always be an outer loop containing the Root and Return nodes.
2779   // If not, we have a degenerate empty program.  Bail out in this case.
2780   if (!has_node(C->root())) {
2781     if (!_verify_only) {
2782       C->clear_major_progress();
2783       C->record_method_not_compilable("empty program detected during loop optimization");
2784     }
2785     return;
2786   }
2787 
2788   // Nothing to do, so get out
2789   bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !_verify_me && !_verify_only && !shenandoah_opts;
2790   bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
2791   if (stop_early && !do_expensive_nodes) {
2792     _igvn.optimize();           // Cleanup NeverBranches
2793     return;
2794   }
2795 
2796   // Set loop nesting depth
2797   _ltree_root->set_nest( 0 );
2798 
2799   // Split shared headers and insert loop landing pads.
2800   // Do not bother doing this on the Root loop of course.
2801   if( !_verify_me && !_verify_only && _ltree_root->_child ) {
2802     C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
2803     if( _ltree_root->_child->beautify_loops( this ) ) {
2804       // Re-build loop tree!
2805       _ltree_root->_child = NULL;
2806       _nodes.clear();
2807       reallocate_preorders();
2808       build_loop_tree();
2809       // Check for bailout, and return


2848 
2849   // Walk the DATA nodes and place into loops.  Find earliest control
2850   // node.  For CFG nodes, the _nodes array starts out and remains
2851   // holding the associated IdealLoopTree pointer.  For DATA nodes, the
2852   // _nodes array holds the earliest legal controlling CFG node.
2853 
2854   // Allocate stack with enough space to avoid frequent realloc
2855   int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
2856   Node_Stack nstack( a, stack_size );
2857 
2858   visited.Clear();
2859   Node_List worklist(a);
2860   // Don't need C->root() on worklist since
2861   // it will be processed among C->top() inputs
2862   worklist.push( C->top() );
2863   visited.set( C->top()->_idx ); // Set C->top() as visited now
2864   build_loop_early( visited, worklist, nstack );
2865 
2866   // Given early legal placement, try finding counted loops.  This placement
2867   // is good enough to discover most loop invariants.
2868   if (!_verify_me && !_verify_only && !shenandoah_opts) {
2869     _ltree_root->counted_loop(this);
2870   }
2871 
2872   // Find latest loop placement.  Find ideal loop placement.
2873   visited.Clear();
2874   init_dom_lca_tags();
2875   // Need C->root() on worklist when processing outs
2876   worklist.push( C->root() );
2877   NOT_PRODUCT( C->verify_graph_edges(); )
2878   worklist.push( C->top() );
2879   build_loop_late(visited, worklist, nstack, !shenandoah_opts);
2880 
2881   if (_verify_only) {
2882     // restore major progress flag
2883     for (int i = 0; i < old_progress; i++)
2884       C->set_major_progress();
2885     assert(C->unique() == unique, "verification mode made Nodes? ? ?");
2886     assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
2887     return;
2888   }
2889 
2890   // clear out the dead code after build_loop_late
2891   while (_deadlist.size()) {
2892     _igvn.remove_globally_dead_node(_deadlist.pop());
2893   }
2894 
2895   if (stop_early) {
2896     assert(do_expensive_nodes, "why are we here?");
2897     if (process_expensive_nodes()) {
2898       // If we made some progress when processing expensive nodes then
2899       // the IGVN may modify the graph in a way that will allow us to


2921   if(TraceLoopOpts && C->has_loops()) {
2922     _ltree_root->dump();
2923   }
2924 #endif
2925 
2926   if (skip_loop_opts) {
2927     // restore major progress flag
2928     for (int i = 0; i < old_progress; i++) {
2929       C->set_major_progress();
2930     }
2931 
2932     // Cleanup any modified bits
2933     _igvn.optimize();
2934 
2935     if (C->log() != NULL) {
2936       log_loop_tree(_ltree_root, _ltree_root, C->log());
2937     }
2938     return;
2939   }
2940 
2941 #if INCLUDE_SHENANDOAHGC
2942   if (UseShenandoahGC && ((ShenandoahBarrierSetC2*) BarrierSet::barrier_set()->barrier_set_c2())->optimize_loops(this, mode, visited, nstack, worklist)) {
2943     _igvn.optimize();
2944     if (C->log() != NULL) {
2945       log_loop_tree(_ltree_root, _ltree_root, C->log());
2946     }
2947     return;
2948   }
2949 #endif
2950 
2951   if (ReassociateInvariants) {
2952     // Reassociate invariants and prep for split_thru_phi
2953     for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2954       IdealLoopTree* lpt = iter.current();
2955       bool is_counted = lpt->is_counted();
2956       if (!is_counted || !lpt->is_inner()) continue;
2957 
2958       // check for vectorized loops, any reassociation of invariants was already done
2959       if (is_counted && lpt->_head->as_CountedLoop()->do_unroll_only()) continue;
2960 
2961       lpt->reassociate_invariants(this);
2962 
2963       // Because RCE opportunities can be masked by split_thru_phi,
2964       // look for RCE candidates and inhibit split_thru_phi
2965       // on just their loop-phi's for this pass of loop opts
2966       if (SplitIfBlocks && do_split_ifs) {
2967         if (lpt->policy_range_check(this)) {
2968           lpt->_rce_candidate = 1; // = true
2969         }
2970       }
2971     }
2972   }
2973 
2974   // Check for aggressive application of split-if and other transforms
2975   // that require basic-block info (like cloning through Phi's)
2976   if( SplitIfBlocks && do_split_ifs ) {
2977     visited.Clear();
2978     split_if_with_blocks( visited, nstack, mode == LoopOptsZgcLastRound );
2979     NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); );
2980     if (mode == LoopOptsZgcLastRound) {
2981       C->set_major_progress();
2982     }
2983   }
2984 
2985   if (!C->major_progress() && do_expensive_nodes && process_expensive_nodes()) {
2986     C->set_major_progress();
2987   }
2988 
2989   // Perform loop predication before iteration splitting
2990   if (C->has_loops() && !C->major_progress() && (C->predicate_count() > 0)) {
2991     _ltree_root->_child->loop_predication(this);
2992   }
2993 
2994   if (OptimizeFill && UseLoopPredicate && C->has_loops() && !C->major_progress()) {
2995     if (do_intrinsify_fill()) {
2996       C->set_major_progress();
2997     }
2998   }
2999 
3000   // Perform iteration-splitting on inner loops.  Split iterations to avoid


3961     compute_lca_of_uses(n, early, true);
3962   }
3963 #endif
3964 
3965   // if this is a load, check for anti-dependent stores
3966   // We use a conservative algorithm to identify potential interfering
3967   // instructions and for rescheduling the load.  The users of the memory
3968   // input of this load are examined.  Any use which is not a load and is
3969   // dominated by early is considered a potentially interfering store.
3970   // This can produce false positives.
3971   if (n->is_Load() && LCA != early) {
3972     Node_List worklist;
3973 
3974     Node *mem = n->in(MemNode::Memory);
3975     for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
3976       Node* s = mem->fast_out(i);
3977       worklist.push(s);
3978     }
3979     while(worklist.size() != 0 && LCA != early) {
3980       Node* s = worklist.pop();
3981       if (s->is_Load() || s->is_ShenandoahBarrier() || s->Opcode() == Op_SafePoint ||
3982           (UseShenandoahGC && s->is_CallStaticJava() && s->as_CallStaticJava()->uncommon_trap_request() != 0)) {
3983         continue;
3984       } else if (s->is_MergeMem()) {
3985         for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) {
3986           Node* s1 = s->fast_out(i);
3987           worklist.push(s1);
3988         }
3989       } else {
3990         Node *sctrl = has_ctrl(s) ? get_ctrl(s) : s->in(0);
3991         assert(sctrl != NULL || s->outcnt() == 0, "must have control");
3992         if (sctrl != NULL && !sctrl->is_top() && is_dominator(early, sctrl)) {
3993           LCA = dom_lca_for_get_late_ctrl(LCA, sctrl, n);
3994         }
3995       }
3996     }
3997   }
3998 
3999   assert(LCA == find_non_split_ctrl(LCA), "unexpected late control");
4000   return LCA;
4001 }
4002 


4089 }
4090 
4091 //------------------------------clear_dom_lca_tags------------------------------
4092 // Tag could be a node's integer index, 32bits instead of 64bits in some cases
4093 // Intended use does not involve any growth for the array, so it could
4094 // be of fixed size.
4095 void PhaseIdealLoop::clear_dom_lca_tags() {
4096   uint limit = C->unique() + 1;
4097   _dom_lca_tags.map( limit, NULL );
4098   _dom_lca_tags.clear();
4099 #ifdef ASSERT
4100   for( uint i = 0; i < limit; ++i ) {
4101     assert(_dom_lca_tags[i] == NULL, "Must be distinct from each node pointer");
4102   }
4103 #endif // ASSERT
4104 }
4105 
4106 //------------------------------build_loop_late--------------------------------
4107 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
4108 // Second pass finds latest legal placement, and ideal loop placement.
4109 void PhaseIdealLoop::build_loop_late(VectorSet &visited, Node_List &worklist, Node_Stack &nstack, bool verify_strip_mined) {
4110   while (worklist.size() != 0) {
4111     Node *n = worklist.pop();
4112     // Only visit once
4113     if (visited.test_set(n->_idx)) continue;
4114     uint cnt = n->outcnt();
4115     uint   i = 0;
4116     while (true) {
4117       assert( _nodes[n->_idx], "no dead nodes" );
4118       // Visit all children
4119       if (i < cnt) {
4120         Node* use = n->raw_out(i);
4121         ++i;
4122         // Check for dead uses.  Aggressively prune such junk.  It might be
4123         // dead in the global sense, but still have local uses so I cannot
4124         // easily call 'remove_dead_node'.
4125         if( _nodes[use->_idx] != NULL || use->is_top() ) { // Not dead?
4126           // Due to cycles, we might not hit the same fixed point in the verify
4127           // pass as we do in the regular pass.  Instead, visit such phis as
4128           // simple uses of the loop head.
4129           if( use->in(0) && (use->is_CFG() || use->is_Phi()) ) {
4130             if( !visited.test(use->_idx) )
4131               worklist.push(use);
4132           } else if( !visited.test_set(use->_idx) ) {
4133             nstack.push(n, i); // Save parent and next use's index.
4134             n   = use;         // Process all children of current use.
4135             cnt = use->outcnt();
4136             i   = 0;
4137           }
4138         } else {
4139           // Do not visit around the backedge of loops via data edges.
4140           // push dead code onto a worklist
4141           _deadlist.push(use);
4142         }
4143       } else {
4144         // All of n's children have been processed, complete post-processing.
4145         build_loop_late_post(n, verify_strip_mined);
4146         if (nstack.is_empty()) {
4147           // Finished all nodes on stack.
4148           // Process next node on the worklist.
4149           break;
4150         }
4151         // Get saved parent node and next use's index. Visit the rest of uses.
4152         n   = nstack.node();
4153         cnt = n->outcnt();
4154         i   = nstack.index();
4155         nstack.pop();
4156       }
4157     }
4158   }
4159 }
4160 
4161 // Verify that no data node is schedules in the outer loop of a strip
4162 // mined loop.
4163 void PhaseIdealLoop::verify_strip_mined_scheduling(Node *n, Node* least) {
4164 #ifdef ASSERT
4165   if (get_loop(least)->_nest == 0) {


4176       Node *m = wq.at(i);
4177       for (uint i = 1; i < m->req(); i++) {
4178         Node* nn = m->in(i);
4179         if (nn == n) {
4180           return;
4181         }
4182         if (nn != NULL && has_ctrl(nn) && get_loop(get_ctrl(nn)) == loop) {
4183           wq.push(nn);
4184         }
4185       }
4186     }
4187     ShouldNotReachHere();
4188   }
4189 #endif
4190 }
4191 
4192 
4193 //------------------------------build_loop_late_post---------------------------
4194 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
4195 // Second pass finds latest legal placement, and ideal loop placement.
4196 void PhaseIdealLoop::build_loop_late_post(Node *n, bool verify_strip_mined) {
4197 
4198   if (n->req() == 2 && (n->Opcode() == Op_ConvI2L || n->Opcode() == Op_CastII) && !C->major_progress() && !_verify_only) {
4199     _igvn._worklist.push(n);  // Maybe we'll normalize it, if no more loops.
4200   }
4201 
4202 #ifdef ASSERT
4203   if (_verify_only && !n->is_CFG()) {
4204     // Check def-use domination.
4205     compute_lca_of_uses(n, get_ctrl(n), true /* verify */);
4206   }
4207 #endif
4208 
4209   // CFG and pinned nodes already handled
4210   if( n->in(0) ) {
4211     if( n->in(0)->is_top() ) return; // Dead?
4212 
4213     // We'd like +VerifyLoopOptimizations to not believe that Mod's/Loads
4214     // _must_ be pinned (they have to observe their control edge of course).
4215     // Unlike Stores (which modify an unallocable resource, the memory
4216     // state), Mods/Loads can float around.  So free them up.


4332     }
4333   }
4334 
4335 #ifdef ASSERT
4336   // If verifying, verify that 'verify_me' has a legal location
4337   // and choose it as our location.
4338   if( _verify_me ) {
4339     Node *v_ctrl = _verify_me->get_ctrl_no_update(n);
4340     Node *legal = LCA;
4341     while( early != legal ) {   // While not at earliest legal
4342       if( legal == v_ctrl ) break;  // Check for prior good location
4343       legal = idom(legal)      ;// Bump up the IDOM tree
4344     }
4345     // Check for prior good location
4346     if( legal == v_ctrl ) least = legal; // Keep prior if found
4347   }
4348 #endif
4349 
4350   // Assign discovered "here or above" point
4351   least = find_non_split_ctrl(least);
4352   if (verify_strip_mined && !_verify_only) {
4353     verify_strip_mined_scheduling(n, least);
4354   }
4355   set_ctrl(n, least);
4356 
4357   // Collect inner loop bodies
4358   IdealLoopTree *chosen_loop = get_loop(least);
4359   if( !chosen_loop->_child )   // Inner loop?
4360     chosen_loop->_body.push(n);// Collect inner loops
4361 }
4362 
4363 #ifdef ASSERT
4364 void PhaseIdealLoop::dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA) {
4365   tty->print_cr("%s", msg);
4366   tty->print("n: "); n->dump();
4367   tty->print("early(n): "); early->dump();
4368   if (n->in(0) != NULL  && !n->in(0)->is_top() &&
4369       n->in(0) != early && !n->in(0)->is_Root()) {
4370     tty->print("n->in(0): "); n->in(0)->dump();
4371   }
4372   for (uint i = 1; i < n->req(); i++) {
4373     Node* in1 = n->in(i);
4374     if (in1 != NULL && in1 != n && !in1->is_top()) {


4496     }
4497     // Dump nodes it controls
4498     for( uint k = 0; k < _nodes.Size(); k++ ) {
4499       // (k < C->unique() && get_ctrl(find(k)) == n)
4500       if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
4501         Node *m = C->root()->find(k);
4502         if( m && m->outcnt() > 0 ) {
4503           if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
4504             tty->print_cr("*** BROKEN CTRL ACCESSOR!  _nodes[k] is %p, ctrl is %p",
4505                           _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
4506           }
4507           for( uint j = 0; j < loop->_nest; j++ )
4508             tty->print("  ");
4509           tty->print(" ");
4510           m->dump();
4511         }
4512       }
4513     }
4514   }
4515 }
4516 #endif
4517 
4518 // Collect a R-P-O for the whole CFG.
4519 // Result list is in post-order (scan backwards for RPO)
4520 void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const {
4521   stk.push(start, 0);
4522   visited.set(start->_idx);
4523 
4524   while (stk.is_nonempty()) {
4525     Node* m   = stk.node();
4526     uint  idx = stk.index();
4527     if (idx < m->outcnt()) {
4528       stk.set_index(idx + 1);
4529       Node* n = m->raw_out(idx);
4530       if (n->is_CFG() && !visited.test_set(n->_idx)) {
4531         stk.push(n, 0);
4532       }
4533     } else {
4534       rpo_list.push(m);
4535       stk.pop();
4536     }
4537   }
4538 }

4539 
4540 
4541 //=============================================================================
4542 //------------------------------LoopTreeIterator-----------------------------------
4543 
4544 // Advance to next loop tree using a preorder, left-to-right traversal.
4545 void LoopTreeIterator::next() {
4546   assert(!done(), "must not be done.");
4547   if (_curnt->_child != NULL) {
4548     _curnt = _curnt->_child;
4549   } else if (_curnt->_next != NULL) {
4550     _curnt = _curnt->_next;
4551   } else {
4552     while (_curnt != _root && _curnt->_next == NULL) {
4553       _curnt = _curnt->_parent;
4554     }
4555     if (_curnt == _root) {
4556       _curnt = NULL;
4557       assert(done(), "must be done.");
4558     } else {
< prev index next >