< prev index next >

src/share/vm/opto/loopnode.cpp

Print this page




  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 "ci/ciMethodData.hpp"
  27 #include "compiler/compileLog.hpp"
  28 #include "libadt/vectset.hpp"
  29 #include "memory/allocation.inline.hpp"
  30 #include "opto/addnode.hpp"
  31 #include "opto/callnode.hpp"
  32 #include "opto/connode.hpp"
  33 #include "opto/divnode.hpp"
  34 #include "opto/idealGraphPrinter.hpp"
  35 #include "opto/loopnode.hpp"
  36 #include "opto/mulnode.hpp"
  37 #include "opto/rootnode.hpp"
  38 #include "opto/superword.hpp"
  39 




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


2338 
2339 #ifndef PRODUCT
2340   C->verify_graph_edges();
2341   if (_verify_me) {             // Nested verify pass?
2342     // Check to see if the verify mode is broken
2343     assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
2344     return;
2345   }
2346   if(VerifyLoopOptimizations) verify();
2347   if(TraceLoopOpts && C->has_loops()) {
2348     _ltree_root->dump();
2349   }
2350 #endif
2351 
2352   if (skip_loop_opts) {
2353     // restore major progress flag
2354     for (int i = 0; i < old_progress; i++) {
2355       C->set_major_progress();
2356     }
2357 






2358     // Cleanup any modified bits
2359     _igvn.optimize();
2360 
2361     if (C->log() != NULL) {
2362       log_loop_tree(_ltree_root, _ltree_root, C->log());
2363     }
2364     return;
2365   }
2366 
2367   if (ReassociateInvariants) {
2368     // Reassociate invariants and prep for split_thru_phi
2369     for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2370       IdealLoopTree* lpt = iter.current();
2371       if (!lpt->is_counted() || !lpt->is_inner()) continue;
2372 
2373       lpt->reassociate_invariants(this);
2374 
2375       // Because RCE opportunities can be masked by split_thru_phi,
2376       // look for RCE candidates and inhibit split_thru_phi
2377       // on just their loop-phi's for this pass of loop opts


3329     compute_lca_of_uses(n, early, true);
3330   }
3331 #endif
3332 
3333   // if this is a load, check for anti-dependent stores
3334   // We use a conservative algorithm to identify potential interfering
3335   // instructions and for rescheduling the load.  The users of the memory
3336   // input of this load are examined.  Any use which is not a load and is
3337   // dominated by early is considered a potentially interfering store.
3338   // This can produce false positives.
3339   if (n->is_Load() && LCA != early) {
3340     Node_List worklist;
3341 
3342     Node *mem = n->in(MemNode::Memory);
3343     for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
3344       Node* s = mem->fast_out(i);
3345       worklist.push(s);
3346     }
3347     while(worklist.size() != 0 && LCA != early) {
3348       Node* s = worklist.pop();
3349       if (s->is_Load()) {



3350         continue;
3351       } else if (s->is_MergeMem()) {
3352         for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) {
3353           Node* s1 = s->fast_out(i);
3354           worklist.push(s1);
3355         }
3356       } else {
3357         Node *sctrl = has_ctrl(s) ? get_ctrl(s) : s->in(0);
3358         assert(sctrl != NULL || s->outcnt() == 0, "must have control");
3359         if (sctrl != NULL && !sctrl->is_top() && is_dominator(early, sctrl)) {
3360           LCA = dom_lca_for_get_late_ctrl(LCA, sctrl, n);
3361         }
3362       }
3363     }
3364   }
3365 
3366   assert(LCA == find_non_split_ctrl(LCA), "unexpected late control");
3367   return LCA;
3368 }
3369 


3561     case Op_LoadUB:             // during loop optimizations.
3562     case Op_LoadUS:
3563     case Op_LoadD:
3564     case Op_LoadF:
3565     case Op_LoadI:
3566     case Op_LoadKlass:
3567     case Op_LoadNKlass:
3568     case Op_LoadL:
3569     case Op_LoadS:
3570     case Op_LoadP:
3571     case Op_LoadN:
3572     case Op_LoadRange:
3573     case Op_LoadD_unaligned:
3574     case Op_LoadL_unaligned:
3575     case Op_StrComp:            // Does a bunch of load-like effects
3576     case Op_StrEquals:
3577     case Op_StrIndexOf:
3578     case Op_AryEq:
3579       pinned = false;
3580     }



3581     if( pinned ) {
3582       IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
3583       if( !chosen_loop->_child )       // Inner loop?
3584         chosen_loop->_body.push(n); // Collect inner loops
3585       return;
3586     }
3587   } else {                      // No slot zero
3588     if( n->is_CFG() ) {         // CFG with no slot 0 is dead
3589       _nodes.map(n->_idx,0);    // No block setting, it's globally dead
3590       return;
3591     }
3592     assert(!n->is_CFG() || n->outcnt() == 0, "");
3593   }
3594 
3595   // Do I have a "safe range" I can select over?
3596   Node *early = get_ctrl(n);// Early location already computed
3597 
3598   // Compute latest point this Node can go
3599   Node *LCA = get_late_ctrl( n, early );
3600   // LCA is NULL due to uses being dead


3615   while( early != legal ) {     // While not at earliest legal
3616 #ifdef ASSERT
3617     if (legal->is_Start() && !early->is_Root()) {
3618       // Bad graph. Print idom path and fail.
3619       dump_bad_graph("Bad graph detected in build_loop_late", n, early, LCA);
3620       assert(false, "Bad graph detected in build_loop_late");
3621     }
3622 #endif
3623     // Find least loop nesting depth
3624     legal = idom(legal);        // Bump up the IDOM tree
3625     // Check for lower nesting depth
3626     if( get_loop(legal)->_nest < get_loop(least)->_nest )
3627       least = legal;
3628   }
3629   assert(early == legal || legal != C->root(), "bad dominance of inputs");
3630 
3631   // Try not to place code on a loop entry projection
3632   // which can inhibit range check elimination.
3633   if (least != early) {
3634     Node* ctrl_out = least->unique_ctrl_out();
3635     if (ctrl_out && ctrl_out->is_CountedLoop() &&
3636         least == ctrl_out->in(LoopNode::EntryControl)) {



























3637       Node* least_dom = idom(least);
3638       if (get_loop(least_dom)->is_member(get_loop(least))) {
3639         least = least_dom;
3640       }
3641     }
3642   }
3643 
3644 #ifdef ASSERT
3645   // If verifying, verify that 'verify_me' has a legal location
3646   // and choose it as our location.
3647   if( _verify_me ) {
3648     Node *v_ctrl = _verify_me->get_ctrl_no_update(n);
3649     Node *legal = LCA;
3650     while( early != legal ) {   // While not at earliest legal
3651       if( legal == v_ctrl ) break;  // Check for prior good location
3652       legal = idom(legal)      ;// Bump up the IDOM tree
3653     }
3654     // Check for prior good location
3655     if( legal == v_ctrl ) least = legal; // Keep prior if found
3656   }


3802     }
3803     // Dump nodes it controls
3804     for( uint k = 0; k < _nodes.Size(); k++ ) {
3805       // (k < C->unique() && get_ctrl(find(k)) == n)
3806       if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
3807         Node *m = C->root()->find(k);
3808         if( m && m->outcnt() > 0 ) {
3809           if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
3810             tty->print_cr("*** BROKEN CTRL ACCESSOR!  _nodes[k] is %p, ctrl is %p",
3811                           _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
3812           }
3813           for( uint j = 0; j < loop->_nest; j++ )
3814             tty->print("  ");
3815           tty->print(" ");
3816           m->dump();
3817         }
3818       }
3819     }
3820   }
3821 }

3822 
3823 // Collect a R-P-O for the whole CFG.
3824 // Result list is in post-order (scan backwards for RPO)
3825 void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const {
3826   stk.push(start, 0);
3827   visited.set(start->_idx);
3828 
3829   while (stk.is_nonempty()) {
3830     Node* m   = stk.node();
3831     uint  idx = stk.index();
3832     if (idx < m->outcnt()) {
3833       stk.set_index(idx + 1);
3834       Node* n = m->raw_out(idx);
3835       if (n->is_CFG() && !visited.test_set(n->_idx)) {
3836         stk.push(n, 0);
3837       }
3838     } else {
3839       rpo_list.push(m);
3840       stk.pop();
3841     }
3842   }
3843 }
3844 #endif
3845 
3846 
3847 //=============================================================================
3848 //------------------------------LoopTreeIterator-----------------------------------
3849 
3850 // Advance to next loop tree using a preorder, left-to-right traversal.
3851 void LoopTreeIterator::next() {
3852   assert(!done(), "must not be done.");
3853   if (_curnt->_child != NULL) {
3854     _curnt = _curnt->_child;
3855   } else if (_curnt->_next != NULL) {
3856     _curnt = _curnt->_next;
3857   } else {
3858     while (_curnt != _root && _curnt->_next == NULL) {
3859       _curnt = _curnt->_parent;
3860     }
3861     if (_curnt == _root) {
3862       _curnt = NULL;
3863       assert(done(), "must be done.");
3864     } else {


  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 "ci/ciMethodData.hpp"
  27 #include "compiler/compileLog.hpp"
  28 #include "libadt/vectset.hpp"
  29 #include "memory/allocation.inline.hpp"
  30 #include "opto/addnode.hpp"
  31 #include "opto/callnode.hpp"
  32 #include "opto/connode.hpp"
  33 #include "opto/divnode.hpp"
  34 #include "opto/idealGraphPrinter.hpp"
  35 #include "opto/loopnode.hpp"
  36 #include "opto/mulnode.hpp"
  37 #include "opto/rootnode.hpp"
  38 #include "opto/superword.hpp"
  39 
  40 #if INCLUDE_ALL_GCS
  41 #include "gc_implementation/shenandoah/c2/shenandoahSupport.hpp"
  42 #endif
  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 {
  63   if (is_inner_loop()) st->print( "inner " );


2342 
2343 #ifndef PRODUCT
2344   C->verify_graph_edges();
2345   if (_verify_me) {             // Nested verify pass?
2346     // Check to see if the verify mode is broken
2347     assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
2348     return;
2349   }
2350   if(VerifyLoopOptimizations) verify();
2351   if(TraceLoopOpts && C->has_loops()) {
2352     _ltree_root->dump();
2353   }
2354 #endif
2355 
2356   if (skip_loop_opts) {
2357     // restore major progress flag
2358     for (int i = 0; i < old_progress; i++) {
2359       C->set_major_progress();
2360     }
2361 
2362 #if INCLUDE_ALL_GCS
2363     if (UseShenandoahGC && !C->major_progress()) {
2364       ShenandoahBarrierC2Support::pin_and_expand(this);
2365     }
2366 #endif
2367 
2368     // Cleanup any modified bits
2369     _igvn.optimize();
2370 
2371     if (C->log() != NULL) {
2372       log_loop_tree(_ltree_root, _ltree_root, C->log());
2373     }
2374     return;
2375   }
2376 
2377   if (ReassociateInvariants) {
2378     // Reassociate invariants and prep for split_thru_phi
2379     for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2380       IdealLoopTree* lpt = iter.current();
2381       if (!lpt->is_counted() || !lpt->is_inner()) continue;
2382 
2383       lpt->reassociate_invariants(this);
2384 
2385       // Because RCE opportunities can be masked by split_thru_phi,
2386       // look for RCE candidates and inhibit split_thru_phi
2387       // on just their loop-phi's for this pass of loop opts


3339     compute_lca_of_uses(n, early, true);
3340   }
3341 #endif
3342 
3343   // if this is a load, check for anti-dependent stores
3344   // We use a conservative algorithm to identify potential interfering
3345   // instructions and for rescheduling the load.  The users of the memory
3346   // input of this load are examined.  Any use which is not a load and is
3347   // dominated by early is considered a potentially interfering store.
3348   // This can produce false positives.
3349   if (n->is_Load() && LCA != early) {
3350     Node_List worklist;
3351 
3352     Node *mem = n->in(MemNode::Memory);
3353     for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
3354       Node* s = mem->fast_out(i);
3355       worklist.push(s);
3356     }
3357     while(worklist.size() != 0 && LCA != early) {
3358       Node* s = worklist.pop();
3359       if (s->is_Load() ||
3360           (UseShenandoahGC &&
3361            (s->is_ShenandoahBarrier() || s->Opcode() == Op_SafePoint ||
3362             (s->is_CallStaticJava() && s->as_CallStaticJava()->uncommon_trap_request() != 0)))) {
3363         continue;
3364       } else if (s->is_MergeMem()) {
3365         for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) {
3366           Node* s1 = s->fast_out(i);
3367           worklist.push(s1);
3368         }
3369       } else {
3370         Node *sctrl = has_ctrl(s) ? get_ctrl(s) : s->in(0);
3371         assert(sctrl != NULL || s->outcnt() == 0, "must have control");
3372         if (sctrl != NULL && !sctrl->is_top() && is_dominator(early, sctrl)) {
3373           LCA = dom_lca_for_get_late_ctrl(LCA, sctrl, n);
3374         }
3375       }
3376     }
3377   }
3378 
3379   assert(LCA == find_non_split_ctrl(LCA), "unexpected late control");
3380   return LCA;
3381 }
3382 


3574     case Op_LoadUB:             // during loop optimizations.
3575     case Op_LoadUS:
3576     case Op_LoadD:
3577     case Op_LoadF:
3578     case Op_LoadI:
3579     case Op_LoadKlass:
3580     case Op_LoadNKlass:
3581     case Op_LoadL:
3582     case Op_LoadS:
3583     case Op_LoadP:
3584     case Op_LoadN:
3585     case Op_LoadRange:
3586     case Op_LoadD_unaligned:
3587     case Op_LoadL_unaligned:
3588     case Op_StrComp:            // Does a bunch of load-like effects
3589     case Op_StrEquals:
3590     case Op_StrIndexOf:
3591     case Op_AryEq:
3592       pinned = false;
3593     }
3594     if (UseShenandoahGC && n->is_CMove()) {
3595       pinned = false;
3596     }
3597     if( pinned ) {
3598       IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
3599       if( !chosen_loop->_child )       // Inner loop?
3600         chosen_loop->_body.push(n); // Collect inner loops
3601       return;
3602     }
3603   } else {                      // No slot zero
3604     if( n->is_CFG() ) {         // CFG with no slot 0 is dead
3605       _nodes.map(n->_idx,0);    // No block setting, it's globally dead
3606       return;
3607     }
3608     assert(!n->is_CFG() || n->outcnt() == 0, "");
3609   }
3610 
3611   // Do I have a "safe range" I can select over?
3612   Node *early = get_ctrl(n);// Early location already computed
3613 
3614   // Compute latest point this Node can go
3615   Node *LCA = get_late_ctrl( n, early );
3616   // LCA is NULL due to uses being dead


3631   while( early != legal ) {     // While not at earliest legal
3632 #ifdef ASSERT
3633     if (legal->is_Start() && !early->is_Root()) {
3634       // Bad graph. Print idom path and fail.
3635       dump_bad_graph("Bad graph detected in build_loop_late", n, early, LCA);
3636       assert(false, "Bad graph detected in build_loop_late");
3637     }
3638 #endif
3639     // Find least loop nesting depth
3640     legal = idom(legal);        // Bump up the IDOM tree
3641     // Check for lower nesting depth
3642     if( get_loop(legal)->_nest < get_loop(least)->_nest )
3643       least = legal;
3644   }
3645   assert(early == legal || legal != C->root(), "bad dominance of inputs");
3646 
3647   // Try not to place code on a loop entry projection
3648   // which can inhibit range check elimination.
3649   if (least != early) {
3650     Node* ctrl_out = least->unique_ctrl_out();
3651     if (UseShenandoahGC && ctrl_out && ctrl_out->is_Loop() &&
3652         least == ctrl_out->in(LoopNode::EntryControl)) {
3653       // Move the node above predicates as far up as possible so a
3654       // following pass of loop predication doesn't hoist a predicate
3655       // that depends on it above that node.
3656       Node* new_ctrl = least;
3657       for (;;) {
3658         if (!new_ctrl->is_Proj()) {
3659           break;
3660         }
3661         CallStaticJavaNode* call = new_ctrl->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none);
3662         if (call == NULL) {
3663           break;
3664         }
3665         int req = call->uncommon_trap_request();
3666         Deoptimization::DeoptReason trap_reason = Deoptimization::trap_request_reason(req);
3667         if (trap_reason != Deoptimization::Reason_loop_limit_check &&
3668             trap_reason != Deoptimization::Reason_predicate) {
3669           break;
3670         }
3671         Node* c = new_ctrl->in(0)->in(0);
3672         if (is_dominator(c, early) && c != early) {
3673           break;
3674         }
3675         new_ctrl = c;
3676       }
3677       least = new_ctrl;
3678     } else if (ctrl_out && ctrl_out->is_CountedLoop() &&
3679                least == ctrl_out->in(LoopNode::EntryControl)) {
3680       Node* least_dom = idom(least);
3681       if (get_loop(least_dom)->is_member(get_loop(least))) {
3682         least = least_dom;
3683       }
3684     }
3685   }
3686 
3687 #ifdef ASSERT
3688   // If verifying, verify that 'verify_me' has a legal location
3689   // and choose it as our location.
3690   if( _verify_me ) {
3691     Node *v_ctrl = _verify_me->get_ctrl_no_update(n);
3692     Node *legal = LCA;
3693     while( early != legal ) {   // While not at earliest legal
3694       if( legal == v_ctrl ) break;  // Check for prior good location
3695       legal = idom(legal)      ;// Bump up the IDOM tree
3696     }
3697     // Check for prior good location
3698     if( legal == v_ctrl ) least = legal; // Keep prior if found
3699   }


3845     }
3846     // Dump nodes it controls
3847     for( uint k = 0; k < _nodes.Size(); k++ ) {
3848       // (k < C->unique() && get_ctrl(find(k)) == n)
3849       if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
3850         Node *m = C->root()->find(k);
3851         if( m && m->outcnt() > 0 ) {
3852           if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
3853             tty->print_cr("*** BROKEN CTRL ACCESSOR!  _nodes[k] is %p, ctrl is %p",
3854                           _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
3855           }
3856           for( uint j = 0; j < loop->_nest; j++ )
3857             tty->print("  ");
3858           tty->print(" ");
3859           m->dump();
3860         }
3861       }
3862     }
3863   }
3864 }
3865 #endif
3866 
3867 // Collect a R-P-O for the whole CFG.
3868 // Result list is in post-order (scan backwards for RPO)
3869 void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const {
3870   stk.push(start, 0);
3871   visited.set(start->_idx);
3872 
3873   while (stk.is_nonempty()) {
3874     Node* m   = stk.node();
3875     uint  idx = stk.index();
3876     if (idx < m->outcnt()) {
3877       stk.set_index(idx + 1);
3878       Node* n = m->raw_out(idx);
3879       if (n->is_CFG() && !visited.test_set(n->_idx)) {
3880         stk.push(n, 0);
3881       }
3882     } else {
3883       rpo_list.push(m);
3884       stk.pop();
3885     }
3886   }
3887 }

3888 
3889 
3890 //=============================================================================
3891 //------------------------------LoopTreeIterator-----------------------------------
3892 
3893 // Advance to next loop tree using a preorder, left-to-right traversal.
3894 void LoopTreeIterator::next() {
3895   assert(!done(), "must not be done.");
3896   if (_curnt->_child != NULL) {
3897     _curnt = _curnt->_child;
3898   } else if (_curnt->_next != NULL) {
3899     _curnt = _curnt->_next;
3900   } else {
3901     while (_curnt != _root && _curnt->_next == NULL) {
3902       _curnt = _curnt->_parent;
3903     }
3904     if (_curnt == _root) {
3905       _curnt = NULL;
3906       assert(done(), "must be done.");
3907     } else {
< prev index next >