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