Mercurial > hg > graal-jvmci-8
diff src/share/vm/opto/loopnode.cpp @ 2383:9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
Summary: Add predicates when loop head bytecode is parsed instead of when back branch bytecode is parsed.
Reviewed-by: never
author | kvn |
---|---|
date | Mon, 21 Mar 2011 11:28:14 -0700 |
parents | 194c9fdee631 |
children | 1927db75dd85 |
line wrap: on
line diff
--- a/src/share/vm/opto/loopnode.cpp Mon Mar 21 02:30:49 2011 -0700 +++ b/src/share/vm/opto/loopnode.cpp Mon Mar 21 11:28:14 2011 -0700 @@ -56,12 +56,32 @@ // Dump special per-node info #ifndef PRODUCT void LoopNode::dump_spec(outputStream *st) const { - if( is_inner_loop () ) st->print( "inner " ); - if( is_partial_peel_loop () ) st->print( "partial_peel " ); - if( partial_peel_has_failed () ) st->print( "partial_peel_failed " ); + if (is_inner_loop()) st->print( "inner " ); + if (is_partial_peel_loop()) st->print( "partial_peel " ); + if (partial_peel_has_failed()) st->print( "partial_peel_failed " ); } #endif +//------------------------------is_valid_counted_loop------------------------- +bool LoopNode::is_valid_counted_loop() const { + if (is_CountedLoop()) { + CountedLoopNode* l = as_CountedLoop(); + CountedLoopEndNode* le = l->loopexit(); + if (le != NULL && + le->proj_out(1 /* true */) == l->in(LoopNode::LoopBackControl)) { + Node* phi = l->phi(); + Node* exit = le->proj_out(0 /* false */); + if (exit != NULL && exit->Opcode() == Op_IfFalse && + phi != NULL && phi->is_Phi() && + phi->in(LoopNode::LoopBackControl) == l->incr() && + le->loopnode() == l && le->stride_is_con()) { + return true; + } + } + } + return false; +} + //------------------------------get_early_ctrl--------------------------------- // Compute earliest legal control Node *PhaseIdealLoop::get_early_ctrl( Node *n ) { @@ -142,43 +162,44 @@ } //------------------------------is_counted_loop-------------------------------- -Node *PhaseIdealLoop::is_counted_loop( Node *x, IdealLoopTree *loop ) { +bool PhaseIdealLoop::is_counted_loop( Node *x, IdealLoopTree *loop ) { PhaseGVN *gvn = &_igvn; // Counted loop head must be a good RegionNode with only 3 not NULL // control input edges: Self, Entry, LoopBack. - if ( x->in(LoopNode::Self) == NULL || x->req() != 3 ) - return NULL; + if (x->in(LoopNode::Self) == NULL || x->req() != 3) + return false; Node *init_control = x->in(LoopNode::EntryControl); Node *back_control = x->in(LoopNode::LoopBackControl); - if( init_control == NULL || back_control == NULL ) // Partially dead - return NULL; + if (init_control == NULL || back_control == NULL) // Partially dead + return false; // Must also check for TOP when looking for a dead loop - if( init_control->is_top() || back_control->is_top() ) - return NULL; + if (init_control->is_top() || back_control->is_top()) + return false; // Allow funny placement of Safepoint - if( back_control->Opcode() == Op_SafePoint ) + if (back_control->Opcode() == Op_SafePoint) back_control = back_control->in(TypeFunc::Control); // Controlling test for loop Node *iftrue = back_control; uint iftrue_op = iftrue->Opcode(); - if( iftrue_op != Op_IfTrue && - iftrue_op != Op_IfFalse ) + if (iftrue_op != Op_IfTrue && + iftrue_op != Op_IfFalse) // I have a weird back-control. Probably the loop-exit test is in // the middle of the loop and I am looking at some trailing control-flow // merge point. To fix this I would have to partially peel the loop. - return NULL; // Obscure back-control + return false; // Obscure back-control // Get boolean guarding loop-back test Node *iff = iftrue->in(0); - if( get_loop(iff) != loop || !iff->in(1)->is_Bool() ) return NULL; + if (get_loop(iff) != loop || !iff->in(1)->is_Bool()) + return false; BoolNode *test = iff->in(1)->as_Bool(); BoolTest::mask bt = test->_test._test; float cl_prob = iff->as_If()->_prob; - if( iftrue_op == Op_IfFalse ) { + if (iftrue_op == Op_IfFalse) { bt = BoolTest(bt).negate(); cl_prob = 1.0 - cl_prob; } @@ -186,7 +207,7 @@ Node *cmp = test->in(1); int cmp_op = cmp->Opcode(); if( cmp_op != Op_CmpI ) - return NULL; // Avoid pointer & float compares + return false; // Avoid pointer & float compares // Find the trip-counter increment & limit. Limit must be loop invariant. Node *incr = cmp->in(1); @@ -196,55 +217,64 @@ // need 'loop()' test to tell if limit is loop invariant // --------- - if( !is_member( loop, get_ctrl(incr) ) ) { // Swapped trip counter and limit? - Node *tmp = incr; // Then reverse order into the CmpI + if (!is_member(loop, get_ctrl(incr))) { // Swapped trip counter and limit? + Node *tmp = incr; // Then reverse order into the CmpI incr = limit; limit = tmp; bt = BoolTest(bt).commute(); // And commute the exit test } - if( is_member( loop, get_ctrl(limit) ) ) // Limit must loop-invariant - return NULL; + if (is_member(loop, get_ctrl(limit))) // Limit must be loop-invariant + return false; + if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant + return false; + Node* phi_incr = NULL; // Trip-counter increment must be commutative & associative. - uint incr_op = incr->Opcode(); - if( incr_op == Op_Phi && incr->req() == 3 ) { - incr = incr->in(2); // Assume incr is on backedge of Phi - incr_op = incr->Opcode(); + if (incr->is_Phi()) { + if (incr->as_Phi()->region() != x || incr->req() != 3) + return false; // Not simple trip counter expression + phi_incr = incr; + incr = phi_incr->in(LoopNode::LoopBackControl); // Assume incr is on backedge of Phi + if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant + return false; } + Node* trunc1 = NULL; Node* trunc2 = NULL; const TypeInt* iv_trunc_t = NULL; if (!(incr = CountedLoopNode::match_incr_with_optional_truncation(incr, &trunc1, &trunc2, &iv_trunc_t))) { - return NULL; // Funny increment opcode + return false; // Funny increment opcode } + assert(incr->Opcode() == Op_AddI, "wrong increment code"); // Get merge point Node *xphi = incr->in(1); Node *stride = incr->in(2); - if( !stride->is_Con() ) { // Oops, swap these - if( !xphi->is_Con() ) // Is the other guy a constant? - return NULL; // Nope, unknown stride, bail out + if (!stride->is_Con()) { // Oops, swap these + if (!xphi->is_Con()) // Is the other guy a constant? + return false; // Nope, unknown stride, bail out Node *tmp = xphi; // 'incr' is commutative, so ok to swap xphi = stride; stride = tmp; } - //if( loop(xphi) != l) return NULL;// Merge point is in inner loop?? - if( !xphi->is_Phi() ) return NULL; // Too much math on the trip counter + // Stride must be constant + int stride_con = stride->get_int(); + assert(stride_con != 0, "missed some peephole opt"); + + if (!xphi->is_Phi()) + return false; // Too much math on the trip counter + if (phi_incr != NULL && phi_incr != xphi) + return false; PhiNode *phi = xphi->as_Phi(); - // Stride must be constant - const Type *stride_t = stride->bottom_type(); - int stride_con = stride_t->is_int()->get_con(); - assert( stride_con, "missed some peephole opt" ); - // Phi must be of loop header; backedge must wrap to increment - if( phi->region() != x ) return NULL; - if( trunc1 == NULL && phi->in(LoopNode::LoopBackControl) != incr || - trunc1 != NULL && phi->in(LoopNode::LoopBackControl) != trunc1 ) { - return NULL; + if (phi->region() != x) + return false; + if (trunc1 == NULL && phi->in(LoopNode::LoopBackControl) != incr || + trunc1 != NULL && phi->in(LoopNode::LoopBackControl) != trunc1) { + return false; } Node *init_trip = phi->in(LoopNode::EntryControl); - //if (!init_trip->is_Con()) return NULL; // avoid rolling over MAXINT/MININT // If iv trunc type is smaller than int, check for possible wrap. if (!TypeInt::INT->higher_equal(iv_trunc_t)) { @@ -267,12 +297,12 @@ if (stride_con > 0) { if (iv_trunc_t->_hi - phi_ft->_hi < stride_con || iv_trunc_t->_lo > phi_ft->_lo) { - return NULL; // truncation may occur + return false; // truncation may occur } } else if (stride_con < 0) { if (iv_trunc_t->_lo - phi_ft->_lo > stride_con || iv_trunc_t->_hi < phi_ft->_hi) { - return NULL; // truncation may occur + return false; // truncation may occur } } // No possibility of wrap so truncation can be discarded @@ -281,35 +311,45 @@ assert(trunc1 == NULL && trunc2 == NULL, "no truncation for int"); } + // If the condition is inverted and we will be rolling + // through MININT to MAXINT, then bail out. + if (bt == BoolTest::eq || // Bail out, but this loop trips at most twice! + // Odd stride + bt == BoolTest::ne && stride_con != 1 && stride_con != -1 || + // Count down loop rolls through MAXINT + (bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0 || + // Count up loop rolls through MININT + (bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0 ) { + return false; // Bail out + } + + const TypeInt* init_t = gvn->type(init_trip)->is_int(); + const TypeInt* limit_t = gvn->type(limit)->is_int(); + + if (stride_con > 0) { + long init_p = (long)init_t->_lo + stride_con; + if (init_p > (long)max_jint || init_p > (long)limit_t->_hi) + return false; // cyclic loop or this loop trips only once + } else { + long init_p = (long)init_t->_hi + stride_con; + if (init_p < (long)min_jint || init_p < (long)limit_t->_lo) + return false; // cyclic loop or this loop trips only once + } + // ================================================= // ---- SUCCESS! Found A Trip-Counted Loop! ----- // - // Canonicalize the condition on the test. If we can exactly determine - // the trip-counter exit value, then set limit to that value and use - // a '!=' test. Otherwise use condition '<' for count-up loops and - // '>' for count-down loops. If the condition is inverted and we will - // be rolling through MININT to MAXINT, then bail out. - + assert(x->Opcode() == Op_Loop, "regular loops only"); C->print_method("Before CountedLoop", 3); - // Check for SafePoint on backedge and remove - Node *sfpt = x->in(LoopNode::LoopBackControl); - if( sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) { - lazy_replace( sfpt, iftrue ); - loop->_tail = iftrue; - } - - // If compare points to incr, we are ok. Otherwise the compare // can directly point to the phi; in this case adjust the compare so that // it points to the incr by adjusting the limit. - if( cmp->in(1) == phi || cmp->in(2) == phi ) + if (cmp->in(1) == phi || cmp->in(2) == phi) limit = gvn->transform(new (C, 3) AddINode(limit,stride)); // trip-count for +-tive stride should be: (limit - init_trip + stride - 1)/stride. // Final value for iterator should be: trip_count * stride + init_trip. - const Type *limit_t = limit->bottom_type(); - const Type *init_t = init_trip->bottom_type(); Node *one_p = gvn->intcon( 1); Node *one_m = gvn->intcon(-1); @@ -317,15 +357,15 @@ Node *hook = new (C, 6) Node(6); switch( bt ) { case BoolTest::eq: - return NULL; // Bail out, but this loop trips at most twice! + ShouldNotReachHere(); case BoolTest::ne: // Ahh, the case we desire - if( stride_con == 1 ) + if (stride_con == 1) trip_count = gvn->transform(new (C, 3) SubINode(limit,init_trip)); - else if( stride_con == -1 ) + else if (stride_con == -1) trip_count = gvn->transform(new (C, 3) SubINode(init_trip,limit)); else - return NULL; // Odd stride; must prove we hit limit exactly - set_subtree_ctrl( trip_count ); + ShouldNotReachHere(); + set_subtree_ctrl(trip_count); //_loop.map(trip_count->_idx,loop(limit)); break; case BoolTest::le: // Maybe convert to '<' case @@ -338,7 +378,8 @@ //_loop.map(limit->_idx,limit_loop); // Fall into next case case BoolTest::lt: { // Maybe convert to '!=' case - if( stride_con < 0 ) return NULL; // Count down loop rolls through MAXINT + if (stride_con < 0) // Count down loop rolls through MAXINT + ShouldNotReachHere(); Node *range = gvn->transform(new (C, 3) SubINode(limit,init_trip)); set_subtree_ctrl( range ); hook->init_req(0, range); @@ -367,7 +408,8 @@ //_loop.map(limit->_idx,limit_loop); // Fall into next case case BoolTest::gt: { // Maybe convert to '!=' case - if( stride_con > 0 ) return NULL; // count up loop rolls through MININT + if (stride_con > 0) // count up loop rolls through MININT + ShouldNotReachHere(); Node *range = gvn->transform(new (C, 3) SubINode(limit,init_trip)); set_subtree_ctrl( range ); hook->init_req(0, range); @@ -385,7 +427,7 @@ hook->init_req(3, trip_count); break; } - } + } // switch( bt ) Node *span = gvn->transform(new (C, 3) MulINode(trip_count,stride)); set_subtree_ctrl( span ); @@ -394,83 +436,82 @@ limit = gvn->transform(new (C, 3) AddINode(span,init_trip)); set_subtree_ctrl( limit ); + // Check for SafePoint on backedge and remove + Node *sfpt = x->in(LoopNode::LoopBackControl); + if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) { + lazy_replace( sfpt, iftrue ); + loop->_tail = iftrue; + } + // Build a canonical trip test. // Clone code, as old values may be in use. + Node* nphi = PhiNode::make(x, init_trip, TypeInt::INT); + nphi = _igvn.register_new_node_with_optimizer(nphi); + set_ctrl(nphi, get_ctrl(phi)); + incr = incr->clone(); - incr->set_req(1,phi); + incr->set_req(1,nphi); incr->set_req(2,stride); incr = _igvn.register_new_node_with_optimizer(incr); set_early_ctrl( incr ); - _igvn.hash_delete(phi); - phi->set_req_X( LoopNode::LoopBackControl, incr, &_igvn ); - // If phi type is more restrictive than Int, raise to - // Int to prevent (almost) infinite recursion in igvn - // which can only handle integer types for constants or minint..maxint. - if (!TypeInt::INT->higher_equal(phi->bottom_type())) { - Node* nphi = PhiNode::make(phi->in(0), phi->in(LoopNode::EntryControl), TypeInt::INT); - nphi->set_req(LoopNode::LoopBackControl, phi->in(LoopNode::LoopBackControl)); - nphi = _igvn.register_new_node_with_optimizer(nphi); - set_ctrl(nphi, get_ctrl(phi)); - _igvn.replace_node(phi, nphi); - phi = nphi->as_Phi(); - } + nphi->set_req(LoopNode::LoopBackControl, incr); + _igvn.replace_node(phi, nphi); + phi = nphi->as_Phi(); + cmp = cmp->clone(); cmp->set_req(1,incr); cmp->set_req(2,limit); cmp = _igvn.register_new_node_with_optimizer(cmp); set_ctrl(cmp, iff->in(0)); - Node *tmp = test->clone(); - assert( tmp->is_Bool(), "" ); - test = (BoolNode*)tmp; - (*(BoolTest*)&test->_test)._test = bt; //BoolTest::ne; + test = test->clone()->as_Bool(); + (*(BoolTest*)&test->_test)._test = bt; test->set_req(1,cmp); _igvn.register_new_node_with_optimizer(test); set_ctrl(test, iff->in(0)); - // If the exit test is dead, STOP! - if( test == NULL ) return NULL; - _igvn.hash_delete(iff); - iff->set_req_X( 1, test, &_igvn ); // Replace the old IfNode with a new LoopEndNode - Node *lex = _igvn.register_new_node_with_optimizer(new (C, 2) CountedLoopEndNode( iff->in(0), iff->in(1), cl_prob, iff->as_If()->_fcnt )); + Node *lex = _igvn.register_new_node_with_optimizer(new (C, 2) CountedLoopEndNode( iff->in(0), test, cl_prob, iff->as_If()->_fcnt )); IfNode *le = lex->as_If(); uint dd = dom_depth(iff); set_idom(le, le->in(0), dd); // Update dominance for loop exit set_loop(le, loop); // Get the loop-exit control - Node *if_f = iff->as_If()->proj_out(!(iftrue_op == Op_IfTrue)); + Node *iffalse = iff->as_If()->proj_out(!(iftrue_op == Op_IfTrue)); // Need to swap loop-exit and loop-back control? - if( iftrue_op == Op_IfFalse ) { + if (iftrue_op == Op_IfFalse) { Node *ift2=_igvn.register_new_node_with_optimizer(new (C, 1) IfTrueNode (le)); Node *iff2=_igvn.register_new_node_with_optimizer(new (C, 1) IfFalseNode(le)); loop->_tail = back_control = ift2; set_loop(ift2, loop); - set_loop(iff2, get_loop(if_f)); + set_loop(iff2, get_loop(iffalse)); // Lazy update of 'get_ctrl' mechanism. - lazy_replace_proj( if_f , iff2 ); - lazy_replace_proj( iftrue, ift2 ); + lazy_replace_proj( iffalse, iff2 ); + lazy_replace_proj( iftrue, ift2 ); // Swap names - if_f = iff2; - iftrue = ift2; + iffalse = iff2; + iftrue = ift2; } else { - _igvn.hash_delete(if_f ); + _igvn.hash_delete(iffalse); _igvn.hash_delete(iftrue); - if_f ->set_req_X( 0, le, &_igvn ); - iftrue->set_req_X( 0, le, &_igvn ); + iffalse->set_req_X( 0, le, &_igvn ); + iftrue ->set_req_X( 0, le, &_igvn ); } - set_idom(iftrue, le, dd+1); - set_idom(if_f, le, dd+1); + set_idom(iftrue, le, dd+1); + set_idom(iffalse, le, dd+1); + assert(iff->outcnt() == 0, "should be dead now"); + lazy_replace( iff, le ); // fix 'get_ctrl' // Now setup a new CountedLoopNode to replace the existing LoopNode CountedLoopNode *l = new (C, 3) CountedLoopNode(init_control, back_control); + l->set_unswitch_count(x->as_Loop()->unswitch_count()); // Preserve // The following assert is approximately true, and defines the intention // of can_be_counted_loop. It fails, however, because phase->type // is not yet initialized for this loop and its parts. @@ -491,10 +532,14 @@ // Free up intermediate goo _igvn.remove_dead_node(hook); +#ifdef ASSERT + assert(l->is_valid_counted_loop(), "counted loop shape is messed up"); + assert(l == loop->_head && l->phi() == phi && l->loopexit() == lex, "" ); +#endif + C->print_method("After CountedLoop", 3); - // Return trip counter - return trip_count; + return true; } @@ -1256,17 +1301,98 @@ return true; } +//---------------------------replace_parallel_iv------------------------------- +// Replace parallel induction variable (parallel to trip counter) +void PhaseIdealLoop::replace_parallel_iv(IdealLoopTree *loop) { + assert(loop->_head->is_CountedLoop(), ""); + CountedLoopNode *cl = loop->_head->as_CountedLoop(); + Node *incr = cl->incr(); + if (incr == NULL) + return; // Dead loop? + Node *init = cl->init_trip(); + Node *phi = cl->phi(); + // protect against stride not being a constant + if (!cl->stride_is_con()) + return; + int stride_con = cl->stride_con(); + + PhaseGVN *gvn = &_igvn; + + // Visit all children, looking for Phis + for (DUIterator i = cl->outs(); cl->has_out(i); i++) { + Node *out = cl->out(i); + // Look for other phis (secondary IVs). Skip dead ones + if (!out->is_Phi() || out == phi || !has_node(out)) + continue; + PhiNode* phi2 = out->as_Phi(); + Node *incr2 = phi2->in( LoopNode::LoopBackControl ); + // Look for induction variables of the form: X += constant + if (phi2->region() != loop->_head || + incr2->req() != 3 || + incr2->in(1) != phi2 || + incr2 == incr || + incr2->Opcode() != Op_AddI || + !incr2->in(2)->is_Con()) + continue; + + // Check for parallel induction variable (parallel to trip counter) + // via an affine function. In particular, count-down loops with + // count-up array indices are common. We only RCE references off + // the trip-counter, so we need to convert all these to trip-counter + // expressions. + Node *init2 = phi2->in( LoopNode::EntryControl ); + int stride_con2 = incr2->in(2)->get_int(); + + // The general case here gets a little tricky. We want to find the + // GCD of all possible parallel IV's and make a new IV using this + // GCD for the loop. Then all possible IVs are simple multiples of + // the GCD. In practice, this will cover very few extra loops. + // Instead we require 'stride_con2' to be a multiple of 'stride_con', + // where +/-1 is the common case, but other integer multiples are + // also easy to handle. + int ratio_con = stride_con2/stride_con; + + if ((ratio_con * stride_con) == stride_con2) { // Check for exact + // Convert to using the trip counter. The parallel induction + // variable differs from the trip counter by a loop-invariant + // amount, the difference between their respective initial values. + // It is scaled by the 'ratio_con'. + // Perform local Ideal transformation since in most cases ratio == 1. + Node* ratio = _igvn.intcon(ratio_con); + set_ctrl(ratio, C->root()); + Node* hook = new (C, 3) Node(3); + Node* ratio_init = gvn->transform(new (C, 3) MulINode(init, ratio)); + hook->init_req(0, ratio_init); + Node* diff = gvn->transform(new (C, 3) SubINode(init2, ratio_init)); + hook->init_req(1, diff); + Node* ratio_idx = gvn->transform(new (C, 3) MulINode(phi, ratio)); + hook->init_req(2, ratio_idx); + Node* add = gvn->transform(new (C, 3) AddINode(ratio_idx, diff)); + set_subtree_ctrl(add); + _igvn.replace_node( phi2, add ); + // Free up intermediate goo + _igvn.remove_dead_node(hook); + // Sometimes an induction variable is unused + if (add->outcnt() == 0) { + _igvn.remove_dead_node(add); + } + --i; // deleted this phi; rescan starting with next position + continue; + } + } +} + //------------------------------counted_loop----------------------------------- // Convert to counted loops where possible void IdealLoopTree::counted_loop( PhaseIdealLoop *phase ) { // For grins, set the inner-loop flag here - if( !_child ) { - if( _head->is_Loop() ) _head->as_Loop()->set_inner_loop(); + if (!_child) { + if (_head->is_Loop()) _head->as_Loop()->set_inner_loop(); } - if( _head->is_CountedLoop() || - phase->is_counted_loop( _head, this ) ) { + if (_head->is_CountedLoop() || + phase->is_counted_loop(_head, this)) { _has_sfpt = 1; // Indicate we do not need a safepoint here // Look for a safepoint to remove @@ -1275,79 +1401,9 @@ phase->is_deleteable_safept(n)) phase->lazy_replace(n,n->in(TypeFunc::Control)); - CountedLoopNode *cl = _head->as_CountedLoop(); - Node *incr = cl->incr(); - if( !incr ) return; // Dead loop? - Node *init = cl->init_trip(); - Node *phi = cl->phi(); - // protect against stride not being a constant - if( !cl->stride_is_con() ) return; - int stride_con = cl->stride_con(); - // Look for induction variables - - // Visit all children, looking for Phis - for (DUIterator i = cl->outs(); cl->has_out(i); i++) { - Node *out = cl->out(i); - // Look for other phis (secondary IVs). Skip dead ones - if (!out->is_Phi() || out == phi || !phase->has_node(out)) continue; - PhiNode* phi2 = out->as_Phi(); - Node *incr2 = phi2->in( LoopNode::LoopBackControl ); - // Look for induction variables of the form: X += constant - if( phi2->region() != _head || - incr2->req() != 3 || - incr2->in(1) != phi2 || - incr2 == incr || - incr2->Opcode() != Op_AddI || - !incr2->in(2)->is_Con() ) - continue; - - // Check for parallel induction variable (parallel to trip counter) - // via an affine function. In particular, count-down loops with - // count-up array indices are common. We only RCE references off - // the trip-counter, so we need to convert all these to trip-counter - // expressions. - Node *init2 = phi2->in( LoopNode::EntryControl ); - int stride_con2 = incr2->in(2)->get_int(); + phase->replace_parallel_iv(this); - // The general case here gets a little tricky. We want to find the - // GCD of all possible parallel IV's and make a new IV using this - // GCD for the loop. Then all possible IVs are simple multiples of - // the GCD. In practice, this will cover very few extra loops. - // Instead we require 'stride_con2' to be a multiple of 'stride_con', - // where +/-1 is the common case, but other integer multiples are - // also easy to handle. - int ratio_con = stride_con2/stride_con; - - if( ratio_con * stride_con == stride_con2 ) { // Check for exact - // Convert to using the trip counter. The parallel induction - // variable differs from the trip counter by a loop-invariant - // amount, the difference between their respective initial values. - // It is scaled by the 'ratio_con'. - Compile* C = phase->C; - Node* ratio = phase->_igvn.intcon(ratio_con); - phase->set_ctrl(ratio, C->root()); - Node* ratio_init = new (C, 3) MulINode(init, ratio); - phase->_igvn.register_new_node_with_optimizer(ratio_init, init); - phase->set_early_ctrl(ratio_init); - Node* diff = new (C, 3) SubINode(init2, ratio_init); - phase->_igvn.register_new_node_with_optimizer(diff, init2); - phase->set_early_ctrl(diff); - Node* ratio_idx = new (C, 3) MulINode(phi, ratio); - phase->_igvn.register_new_node_with_optimizer(ratio_idx, phi); - phase->set_ctrl(ratio_idx, cl); - Node* add = new (C, 3) AddINode(ratio_idx, diff); - phase->_igvn.register_new_node_with_optimizer(add); - phase->set_ctrl(add, cl); - phase->_igvn.replace_node( phi2, add ); - // Sometimes an induction variable is unused - if (add->outcnt() == 0) { - phase->_igvn.remove_dead_node(add); - } - --i; // deleted this phi; rescan starting with next position - continue; - } - } } else if (_parent != NULL && !_irreducible) { // Not a counted loop. // Look for a safepoint on the idom-path to remove, preserving the first one @@ -1366,24 +1422,31 @@ } // Recursively - if( _child ) _child->counted_loop( phase ); - if( _next ) _next ->counted_loop( phase ); + if (_child) _child->counted_loop( phase ); + if (_next) _next ->counted_loop( phase ); } #ifndef PRODUCT //------------------------------dump_head-------------------------------------- // Dump 1 liner for loop header info void IdealLoopTree::dump_head( ) const { - for( uint i=0; i<_nest; i++ ) + for (uint i=0; i<_nest; i++) tty->print(" "); tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx); - if( _irreducible ) tty->print(" IRREDUCIBLE"); - if( _head->is_CountedLoop() ) { + if (_irreducible) tty->print(" IRREDUCIBLE"); + if (UseLoopPredicate) { + Node* entry = _head->in(LoopNode::EntryControl); + if (entry != NULL && entry->is_Proj() && + PhaseIdealLoop::is_uncommon_trap_if_pattern(entry->as_Proj(), Deoptimization::Reason_predicate)) { + tty->print(" predicated"); + } + } + if (_head->is_CountedLoop()) { CountedLoopNode *cl = _head->as_CountedLoop(); tty->print(" counted"); - if( cl->is_pre_loop () ) tty->print(" pre" ); - if( cl->is_main_loop() ) tty->print(" main"); - if( cl->is_post_loop() ) tty->print(" post"); + if (cl->is_pre_loop ()) tty->print(" pre" ); + if (cl->is_main_loop()) tty->print(" main"); + if (cl->is_post_loop()) tty->print(" post"); } tty->cr(); } @@ -1392,8 +1455,8 @@ // Dump loops by loop tree void IdealLoopTree::dump( ) const { dump_head(); - if( _child ) _child->dump(); - if( _next ) _next ->dump(); + if (_child) _child->dump(); + if (_next) _next ->dump(); } #endif @@ -1439,19 +1502,19 @@ } // self (only loops that we can apply loop predication may use their predicates) - if (loop->_head->is_Loop() && - !loop->_irreducible && + if (loop->_head->is_Loop() && + !loop->_irreducible && !loop->tail()->is_top()) { - LoopNode *lpn = loop->_head->as_Loop(); + LoopNode* lpn = loop->_head->as_Loop(); Node* entry = lpn->in(LoopNode::EntryControl); - ProjNode *predicate_proj = find_predicate_insertion_point(entry); + Node* predicate_proj = find_predicate(entry); if (predicate_proj != NULL ) { // right pattern that can be used by loop predication - assert(entry->in(0)->in(1)->in(1)->Opcode()==Op_Opaque1, "must be"); + assert(entry->in(0)->in(1)->in(1)->Opcode() == Op_Opaque1, "must be"); useful_predicates.push(entry->in(0)->in(1)->in(1)); // good one } } - if ( loop->_next ) { // sibling + if (loop->_next) { // sibling collect_potentially_useful_predicates(loop->_next, useful_predicates); } } @@ -1459,7 +1522,8 @@ //------------------------eliminate_useless_predicates----------------------------- // Eliminate all inserted predicates if they could not be used by loop predication. void PhaseIdealLoop::eliminate_useless_predicates() { - if (C->predicate_count() == 0) return; // no predicate left + if (C->predicate_count() == 0) + return; // no predicate left Unique_Node_List useful_predicates; // to store useful predicates if (C->has_loops()) { @@ -1647,12 +1711,15 @@ #ifndef PRODUCT C->verify_graph_edges(); - if( _verify_me ) { // Nested verify pass? + if (_verify_me) { // Nested verify pass? // Check to see if the verify mode is broken assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?"); return; } - if( VerifyLoopOptimizations ) verify(); + if(VerifyLoopOptimizations) verify(); + if(TraceLoopOpts && C->has_loops()) { + _ltree_root->dump(); + } #endif if (ReassociateInvariants) {