2213 for( uint i = 1; i < C->root()->req(); i++ ) {
2214 if( !_nodes[C->root()->in(i)->_idx] ) { // Dead path into Root?
2215 _igvn.delete_input_of(C->root(), i);
2216 i--; // Rerun same iteration on compressed edges
2217 }
2218 }
2219
2220 // Given dominators, try to find inner loops with calls that must
2221 // always be executed (call dominates loop tail). These loops do
2222 // not need a separate safepoint.
2223 Node_List cisstack(a);
2224 _ltree_root->check_safepts(visited, cisstack);
2225 }
2226
2227 // Walk the DATA nodes and place into loops. Find earliest control
2228 // node. For CFG nodes, the _nodes array starts out and remains
2229 // holding the associated IdealLoopTree pointer. For DATA nodes, the
2230 // _nodes array holds the earliest legal controlling CFG node.
2231
2232 // Allocate stack with enough space to avoid frequent realloc
2233 int stack_size = (C->unique() >> 1) + 16; // (unique>>1)+16 from Java2D stats
2234 Node_Stack nstack( a, stack_size );
2235
2236 visited.Clear();
2237 Node_List worklist(a);
2238 // Don't need C->root() on worklist since
2239 // it will be processed among C->top() inputs
2240 worklist.push( C->top() );
2241 visited.set( C->top()->_idx ); // Set C->top() as visited now
2242 build_loop_early( visited, worklist, nstack );
2243
2244 // Given early legal placement, try finding counted loops. This placement
2245 // is good enough to discover most loop invariants.
2246 if( !_verify_me && !_verify_only )
2247 _ltree_root->counted_loop( this );
2248
2249 // Find latest loop placement. Find ideal loop placement.
2250 visited.Clear();
2251 init_dom_lca_tags();
2252 // Need C->root() on worklist when processing outs
2253 worklist.push( C->root() );
2669 _idom[idx] = n;
2670 _dom_depth[idx] = dom_depth;
2671 }
2672
2673 //------------------------------recompute_dom_depth---------------------------------------
2674 // The dominator tree is constructed with only parent pointers.
2675 // This recomputes the depth in the tree by first tagging all
2676 // nodes as "no depth yet" marker. The next pass then runs up
2677 // the dom tree from each node marked "no depth yet", and computes
2678 // the depth on the way back down.
2679 void PhaseIdealLoop::recompute_dom_depth() {
2680 uint no_depth_marker = C->unique();
2681 uint i;
2682 // Initialize depth to "no depth yet"
2683 for (i = 0; i < _idom_size; i++) {
2684 if (_dom_depth[i] > 0 && _idom[i] != NULL) {
2685 _dom_depth[i] = no_depth_marker;
2686 }
2687 }
2688 if (_dom_stk == NULL) {
2689 uint init_size = C->unique() / 100; // Guess that 1/100 is a reasonable initial size.
2690 if (init_size < 10) init_size = 10;
2691 _dom_stk = new GrowableArray<uint>(init_size);
2692 }
2693 // Compute new depth for each node.
2694 for (i = 0; i < _idom_size; i++) {
2695 uint j = i;
2696 // Run up the dom tree to find a node with a depth
2697 while (_dom_depth[j] == no_depth_marker) {
2698 _dom_stk->push(j);
2699 j = _idom[j]->_idx;
2700 }
2701 // Compute the depth on the way back down this tree branch
2702 uint dd = _dom_depth[j] + 1;
2703 while (_dom_stk->length() > 0) {
2704 uint j = _dom_stk->pop();
2705 _dom_depth[j] = dd;
2706 dd++;
2707 }
2708 }
2709 }
2759 // helps me construct nested loops with shared headers better.
2760 //
2761 // Once I've done the forward recursion, I do the post-work. For each child
2762 // I check to see if there is a backedge. Backedges define a loop! I
2763 // insert an IdealLoopTree at the target of the backedge.
2764 //
2765 // During the post-work I also check to see if I have several children
2766 // belonging to different loops. If so, then this Node is a decision point
2767 // where control flow can choose to change loop nests. It is at this
2768 // decision point where I can figure out how loops are nested. At this
2769 // time I can properly order the different loop nests from my children.
2770 // Note that there may not be any backedges at the decision point!
2771 //
2772 // Since the decision point can be far removed from the backedges, I can't
2773 // order my loops at the time I discover them. Thus at the decision point
2774 // I need to inspect loop header pre-order numbers to properly nest my
2775 // loops. This means I need to sort my childrens' loops by pre-order.
2776 // The sort is of size number-of-control-children, which generally limits
2777 // it to size 2 (i.e., I just choose between my 2 target loops).
2778 void PhaseIdealLoop::build_loop_tree() {
2779 // Allocate stack of size C->unique()/2 to avoid frequent realloc
2780 GrowableArray <Node *> bltstack(C->unique() >> 1);
2781 Node *n = C->root();
2782 bltstack.push(n);
2783 int pre_order = 1;
2784 int stack_size;
2785
2786 while ( ( stack_size = bltstack.length() ) != 0 ) {
2787 n = bltstack.top(); // Leave node on stack
2788 if ( !is_visited(n) ) {
2789 // ---- Pre-pass Work ----
2790 // Pre-walked but not post-walked nodes need a pre_order number.
2791
2792 set_preorder_visited( n, pre_order ); // set as visited
2793
2794 // ---- Scan over children ----
2795 // Scan first over control projections that lead to loop headers.
2796 // This helps us find inner-to-outer loops with shared headers better.
2797
2798 // Scan children's children for loop headers.
2799 for ( int i = n->outcnt() - 1; i >= 0; --i ) {
2800 Node* m = n->raw_out(i); // Child
3649 }
3650 }
3651 }
3652 tty->cr();
3653 int ct = 0;
3654 Node *dbg_legal = LCA;
3655 while(!dbg_legal->is_Start() && ct < 100) {
3656 tty->print("idom[%d] ",ct); dbg_legal->dump();
3657 ct++;
3658 dbg_legal = idom(dbg_legal);
3659 }
3660 tty->cr();
3661 }
3662 #endif
3663
3664 #ifndef PRODUCT
3665 //------------------------------dump-------------------------------------------
3666 void PhaseIdealLoop::dump( ) const {
3667 ResourceMark rm;
3668 Arena* arena = Thread::current()->resource_area();
3669 Node_Stack stack(arena, C->unique() >> 2);
3670 Node_List rpo_list;
3671 VectorSet visited(arena);
3672 visited.set(C->top()->_idx);
3673 rpo( C->root(), stack, visited, rpo_list );
3674 // Dump root loop indexed by last element in PO order
3675 dump( _ltree_root, rpo_list.size(), rpo_list );
3676 }
3677
3678 void PhaseIdealLoop::dump( IdealLoopTree *loop, uint idx, Node_List &rpo_list ) const {
3679 loop->dump_head();
3680
3681 // Now scan for CFG nodes in the same loop
3682 for( uint j=idx; j > 0; j-- ) {
3683 Node *n = rpo_list[j-1];
3684 if( !_nodes[n->_idx] ) // Skip dead nodes
3685 continue;
3686 if( get_loop(n) != loop ) { // Wrong loop nest
3687 if( get_loop(n)->_head == n && // Found nested loop?
3688 get_loop(n)->_parent == loop )
3689 dump(get_loop(n),rpo_list.size(),rpo_list); // Print it nested-ly
|
2213 for( uint i = 1; i < C->root()->req(); i++ ) {
2214 if( !_nodes[C->root()->in(i)->_idx] ) { // Dead path into Root?
2215 _igvn.delete_input_of(C->root(), i);
2216 i--; // Rerun same iteration on compressed edges
2217 }
2218 }
2219
2220 // Given dominators, try to find inner loops with calls that must
2221 // always be executed (call dominates loop tail). These loops do
2222 // not need a separate safepoint.
2223 Node_List cisstack(a);
2224 _ltree_root->check_safepts(visited, cisstack);
2225 }
2226
2227 // Walk the DATA nodes and place into loops. Find earliest control
2228 // node. For CFG nodes, the _nodes array starts out and remains
2229 // holding the associated IdealLoopTree pointer. For DATA nodes, the
2230 // _nodes array holds the earliest legal controlling CFG node.
2231
2232 // Allocate stack with enough space to avoid frequent realloc
2233 int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
2234 Node_Stack nstack( a, stack_size );
2235
2236 visited.Clear();
2237 Node_List worklist(a);
2238 // Don't need C->root() on worklist since
2239 // it will be processed among C->top() inputs
2240 worklist.push( C->top() );
2241 visited.set( C->top()->_idx ); // Set C->top() as visited now
2242 build_loop_early( visited, worklist, nstack );
2243
2244 // Given early legal placement, try finding counted loops. This placement
2245 // is good enough to discover most loop invariants.
2246 if( !_verify_me && !_verify_only )
2247 _ltree_root->counted_loop( this );
2248
2249 // Find latest loop placement. Find ideal loop placement.
2250 visited.Clear();
2251 init_dom_lca_tags();
2252 // Need C->root() on worklist when processing outs
2253 worklist.push( C->root() );
2669 _idom[idx] = n;
2670 _dom_depth[idx] = dom_depth;
2671 }
2672
2673 //------------------------------recompute_dom_depth---------------------------------------
2674 // The dominator tree is constructed with only parent pointers.
2675 // This recomputes the depth in the tree by first tagging all
2676 // nodes as "no depth yet" marker. The next pass then runs up
2677 // the dom tree from each node marked "no depth yet", and computes
2678 // the depth on the way back down.
2679 void PhaseIdealLoop::recompute_dom_depth() {
2680 uint no_depth_marker = C->unique();
2681 uint i;
2682 // Initialize depth to "no depth yet"
2683 for (i = 0; i < _idom_size; i++) {
2684 if (_dom_depth[i] > 0 && _idom[i] != NULL) {
2685 _dom_depth[i] = no_depth_marker;
2686 }
2687 }
2688 if (_dom_stk == NULL) {
2689 uint init_size = C->live_nodes() / 100; // Guess that 1/100 is a reasonable initial size.
2690 if (init_size < 10) init_size = 10;
2691 _dom_stk = new GrowableArray<uint>(init_size);
2692 }
2693 // Compute new depth for each node.
2694 for (i = 0; i < _idom_size; i++) {
2695 uint j = i;
2696 // Run up the dom tree to find a node with a depth
2697 while (_dom_depth[j] == no_depth_marker) {
2698 _dom_stk->push(j);
2699 j = _idom[j]->_idx;
2700 }
2701 // Compute the depth on the way back down this tree branch
2702 uint dd = _dom_depth[j] + 1;
2703 while (_dom_stk->length() > 0) {
2704 uint j = _dom_stk->pop();
2705 _dom_depth[j] = dd;
2706 dd++;
2707 }
2708 }
2709 }
2759 // helps me construct nested loops with shared headers better.
2760 //
2761 // Once I've done the forward recursion, I do the post-work. For each child
2762 // I check to see if there is a backedge. Backedges define a loop! I
2763 // insert an IdealLoopTree at the target of the backedge.
2764 //
2765 // During the post-work I also check to see if I have several children
2766 // belonging to different loops. If so, then this Node is a decision point
2767 // where control flow can choose to change loop nests. It is at this
2768 // decision point where I can figure out how loops are nested. At this
2769 // time I can properly order the different loop nests from my children.
2770 // Note that there may not be any backedges at the decision point!
2771 //
2772 // Since the decision point can be far removed from the backedges, I can't
2773 // order my loops at the time I discover them. Thus at the decision point
2774 // I need to inspect loop header pre-order numbers to properly nest my
2775 // loops. This means I need to sort my childrens' loops by pre-order.
2776 // The sort is of size number-of-control-children, which generally limits
2777 // it to size 2 (i.e., I just choose between my 2 target loops).
2778 void PhaseIdealLoop::build_loop_tree() {
2779 // Allocate stack of size C->live_nodes()/2 to avoid frequent realloc
2780 GrowableArray <Node *> bltstack(C->live_nodes() >> 1);
2781 Node *n = C->root();
2782 bltstack.push(n);
2783 int pre_order = 1;
2784 int stack_size;
2785
2786 while ( ( stack_size = bltstack.length() ) != 0 ) {
2787 n = bltstack.top(); // Leave node on stack
2788 if ( !is_visited(n) ) {
2789 // ---- Pre-pass Work ----
2790 // Pre-walked but not post-walked nodes need a pre_order number.
2791
2792 set_preorder_visited( n, pre_order ); // set as visited
2793
2794 // ---- Scan over children ----
2795 // Scan first over control projections that lead to loop headers.
2796 // This helps us find inner-to-outer loops with shared headers better.
2797
2798 // Scan children's children for loop headers.
2799 for ( int i = n->outcnt() - 1; i >= 0; --i ) {
2800 Node* m = n->raw_out(i); // Child
3649 }
3650 }
3651 }
3652 tty->cr();
3653 int ct = 0;
3654 Node *dbg_legal = LCA;
3655 while(!dbg_legal->is_Start() && ct < 100) {
3656 tty->print("idom[%d] ",ct); dbg_legal->dump();
3657 ct++;
3658 dbg_legal = idom(dbg_legal);
3659 }
3660 tty->cr();
3661 }
3662 #endif
3663
3664 #ifndef PRODUCT
3665 //------------------------------dump-------------------------------------------
3666 void PhaseIdealLoop::dump( ) const {
3667 ResourceMark rm;
3668 Arena* arena = Thread::current()->resource_area();
3669 Node_Stack stack(arena, C->live_nodes() >> 2);
3670 Node_List rpo_list;
3671 VectorSet visited(arena);
3672 visited.set(C->top()->_idx);
3673 rpo( C->root(), stack, visited, rpo_list );
3674 // Dump root loop indexed by last element in PO order
3675 dump( _ltree_root, rpo_list.size(), rpo_list );
3676 }
3677
3678 void PhaseIdealLoop::dump( IdealLoopTree *loop, uint idx, Node_List &rpo_list ) const {
3679 loop->dump_head();
3680
3681 // Now scan for CFG nodes in the same loop
3682 for( uint j=idx; j > 0; j-- ) {
3683 Node *n = rpo_list[j-1];
3684 if( !_nodes[n->_idx] ) // Skip dead nodes
3685 continue;
3686 if( get_loop(n) != loop ) { // Wrong loop nest
3687 if( get_loop(n)->_head == n && // Found nested loop?
3688 get_loop(n)->_parent == loop )
3689 dump(get_loop(n),rpo_list.size(),rpo_list); // Print it nested-ly
|