1 /*

     2  * Copyright 2000-2007 Sun Microsystems, Inc.  All Rights Reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.

     8  *

     9  * This code is distributed in the hope that it will be useful, but WITHOUT

    10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    12  * version 2 for more details (a copy is included in the LICENSE file that

    13  * accompanied this code).

    14  *

    15  * You should have received a copy of the GNU General Public License version

    16  * 2 along with this work; if not, write to the Free Software Foundation,

    17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    18  *

    19  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    20  * CA 95054 USA or visit www.sun.com if you need additional information or

    21  * have any questions.

    22  *

    23  */

    24 

    25 #include "incls/_precompiled.incl"

    26 #include "incls/_loopTransform.cpp.incl"

    27 

    28 //------------------------------is_loop_exit-----------------------------------

    29 // Given an IfNode, return the loop-exiting projection or NULL if both

    30 // arms remain in the loop.

    31 Node *IdealLoopTree::is_loop_exit(Node *iff) const {

    32   if( iff->outcnt() != 2 ) return NULL; // Ignore partially dead tests

    33   PhaseIdealLoop *phase = _phase;

    34   // Test is an IfNode, has 2 projections.  If BOTH are in the loop

    35   // we need loop unswitching instead of peeling.

    36   if( !is_member(phase->get_loop( iff->raw_out(0) )) )

    37     return iff->raw_out(0);

    38   if( !is_member(phase->get_loop( iff->raw_out(1) )) )

    39     return iff->raw_out(1);

    40   return NULL;

    41 }

    42 

    43 

    44 //=============================================================================

    45 

    46 

    47 //------------------------------record_for_igvn----------------------------

    48 // Put loop body on igvn work list

    49 void IdealLoopTree::record_for_igvn() {

    50   for( uint i = 0; i < _body.size(); i++ ) {

    51     Node *n = _body.at(i);

    52     _phase->_igvn._worklist.push(n);

    53   }

    54 }

    55 

    56 //------------------------------compute_profile_trip_cnt----------------------------

    57 // Compute loop trip count from profile data as

    58 //    (backedge_count + loop_exit_count) / loop_exit_count

    59 void IdealLoopTree::compute_profile_trip_cnt( PhaseIdealLoop *phase ) {

    60   if (!_head->is_CountedLoop()) {

    61     return;

    62   }

    63   CountedLoopNode* head = _head->as_CountedLoop();

    64   if (head->profile_trip_cnt() != COUNT_UNKNOWN) {

    65     return; // Already computed

    66   }

    67   float trip_cnt = (float)max_jint; // default is big

    68 

    69   Node* back = head->in(LoopNode::LoopBackControl);

    70   while (back != head) {

    71     if ((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&

    72         back->in(0) &&

    73         back->in(0)->is_If() &&

    74         back->in(0)->as_If()->_fcnt != COUNT_UNKNOWN &&

    75         back->in(0)->as_If()->_prob != PROB_UNKNOWN) {

    76       break;

    77     }

    78     back = phase->idom(back);

    79   }

    80   if (back != head) {

    81     assert((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&

    82            back->in(0), "if-projection exists");

    83     IfNode* back_if = back->in(0)->as_If();

    84     float loop_back_cnt = back_if->_fcnt * back_if->_prob;

    85 

    86     // Now compute a loop exit count

    87     float loop_exit_cnt = 0.0f;

    88     for( uint i = 0; i < _body.size(); i++ ) {

    89       Node *n = _body[i];

    90       if( n->is_If() ) {

    91         IfNode *iff = n->as_If();

    92         if( iff->_fcnt != COUNT_UNKNOWN && iff->_prob != PROB_UNKNOWN ) {

    93           Node *exit = is_loop_exit(iff);

    94           if( exit ) {

    95             float exit_prob = iff->_prob;

    96             if (exit->Opcode() == Op_IfFalse) exit_prob = 1.0 - exit_prob;

    97             if (exit_prob > PROB_MIN) {

    98               float exit_cnt = iff->_fcnt * exit_prob;

    99               loop_exit_cnt += exit_cnt;

   100             }

   101           }

   102         }

   103       }

   104     }

   105     if (loop_exit_cnt > 0.0f) {

   106       trip_cnt = (loop_back_cnt + loop_exit_cnt) / loop_exit_cnt;

   107     } else {

   108       // No exit count so use

   109       trip_cnt = loop_back_cnt;

   110     }

   111   }

   112 #ifndef PRODUCT

   113   if (TraceProfileTripCount) {

   114     tty->print_cr("compute_profile_trip_cnt  lp: %d cnt: %f\n", head->_idx, trip_cnt);

   115   }

   116 #endif

   117   head->set_profile_trip_cnt(trip_cnt);

   118 }

   119 

   120 //---------------------is_invariant_addition-----------------------------

   121 // Return nonzero index of invariant operand for an Add or Sub

   122 // of (nonconstant) invariant and variant values. Helper for reassoicate_invariants.

   123 int IdealLoopTree::is_invariant_addition(Node* n, PhaseIdealLoop *phase) {

   124   int op = n->Opcode();

   125   if (op == Op_AddI || op == Op_SubI) {

   126     bool in1_invar = this->is_invariant(n->in(1));

   127     bool in2_invar = this->is_invariant(n->in(2));

   128     if (in1_invar && !in2_invar) return 1;

   129     if (!in1_invar && in2_invar) return 2;

   130   }

   131   return 0;

   132 }

   133 

   134 //---------------------reassociate_add_sub-----------------------------

   135 // Reassociate invariant add and subtract expressions:

   136 //

   137 // inv1 + (x + inv2)  =>  ( inv1 + inv2) + x

   138 // (x + inv2) + inv1  =>  ( inv1 + inv2) + x

   139 // inv1 + (x - inv2)  =>  ( inv1 - inv2) + x

   140 // inv1 - (inv2 - x)  =>  ( inv1 - inv2) + x

   141 // (x + inv2) - inv1  =>  (-inv1 + inv2) + x

   142 // (x - inv2) + inv1  =>  ( inv1 - inv2) + x

   143 // (x - inv2) - inv1  =>  (-inv1 - inv2) + x

   144 // inv1 + (inv2 - x)  =>  ( inv1 + inv2) - x

   145 // inv1 - (x - inv2)  =>  ( inv1 + inv2) - x

   146 // (inv2 - x) + inv1  =>  ( inv1 + inv2) - x

   147 // (inv2 - x) - inv1  =>  (-inv1 + inv2) - x

   148 // inv1 - (x + inv2)  =>  ( inv1 - inv2) - x

   149 //

   150 Node* IdealLoopTree::reassociate_add_sub(Node* n1, PhaseIdealLoop *phase) {

   151   if (!n1->is_Add() && !n1->is_Sub() || n1->outcnt() == 0) return NULL;

   152   if (is_invariant(n1)) return NULL;

   153   int inv1_idx = is_invariant_addition(n1, phase);

   154   if (!inv1_idx) return NULL;

   155   // Don't mess with add of constant (igvn moves them to expression tree root.)

   156   if (n1->is_Add() && n1->in(2)->is_Con()) return NULL;

   157   Node* inv1 = n1->in(inv1_idx);

   158   Node* n2 = n1->in(3 - inv1_idx);

   159   int inv2_idx = is_invariant_addition(n2, phase);

   160   if (!inv2_idx) return NULL;

   161   Node* x    = n2->in(3 - inv2_idx);

   162   Node* inv2 = n2->in(inv2_idx);

   163 

   164   bool neg_x    = n2->is_Sub() && inv2_idx == 1;

   165   bool neg_inv2 = n2->is_Sub() && inv2_idx == 2;

   166   bool neg_inv1 = n1->is_Sub() && inv1_idx == 2;

   167   if (n1->is_Sub() && inv1_idx == 1) {

   168     neg_x    = !neg_x;

   169     neg_inv2 = !neg_inv2;

   170   }

   171   Node* inv1_c = phase->get_ctrl(inv1);

   172   Node* inv2_c = phase->get_ctrl(inv2);

   173   Node* n_inv1;

   174   if (neg_inv1) {

   175     Node *zero = phase->_igvn.intcon(0);

   176     phase->set_ctrl(zero, phase->C->root());

   177     n_inv1 = new (phase->C, 3) SubINode(zero, inv1);

   178     phase->register_new_node(n_inv1, inv1_c);

   179   } else {

   180     n_inv1 = inv1;

   181   }

   182   Node* inv;

   183   if (neg_inv2) {

   184     inv = new (phase->C, 3) SubINode(n_inv1, inv2);

   185   } else {

   186     inv = new (phase->C, 3) AddINode(n_inv1, inv2);

   187   }

   188   phase->register_new_node(inv, phase->get_early_ctrl(inv));

   189 

   190   Node* addx;

   191   if (neg_x) {

   192     addx = new (phase->C, 3) SubINode(inv, x);

   193   } else {

   194     addx = new (phase->C, 3) AddINode(x, inv);

   195   }

   196   phase->register_new_node(addx, phase->get_ctrl(x));

   197   phase->_igvn.hash_delete(n1);

   198   phase->_igvn.subsume_node(n1, addx);

   199   return addx;

   200 }

   201 

   202 //---------------------reassociate_invariants-----------------------------

   203 // Reassociate invariant expressions:

   204 void IdealLoopTree::reassociate_invariants(PhaseIdealLoop *phase) {

   205   for (int i = _body.size() - 1; i >= 0; i--) {

   206     Node *n = _body.at(i);

   207     for (int j = 0; j < 5; j++) {

   208       Node* nn = reassociate_add_sub(n, phase);

   209       if (nn == NULL) break;

   210       n = nn; // again

   211     };

   212   }

   213 }

   214 

   215 //------------------------------policy_peeling---------------------------------

   216 // Return TRUE or FALSE if the loop should be peeled or not.  Peel if we can

   217 // make some loop-invariant test (usually a null-check) happen before the loop.

   218 bool IdealLoopTree::policy_peeling( PhaseIdealLoop *phase ) const {

   219   Node *test = ((IdealLoopTree*)this)->tail();

   220   int  body_size = ((IdealLoopTree*)this)->_body.size();

   221   int  uniq      = phase->C->unique();

   222   // Peeling does loop cloning which can result in O(N^2) node construction

   223   if( body_size > 255 /* Prevent overflow for large body_size */

   224       || (body_size * body_size + uniq > MaxNodeLimit) ) {

   225     return false;           // too large to safely clone

   226   }

   227   while( test != _head ) {      // Scan till run off top of loop

   228     if( test->is_If() ) {       // Test?

   229       Node *ctrl = phase->get_ctrl(test->in(1));

   230       if (ctrl->is_top())

   231         return false;           // Found dead test on live IF?  No peeling!

   232       // Standard IF only has one input value to check for loop invariance

   233       assert( test->Opcode() == Op_If || test->Opcode() == Op_CountedLoopEnd, "Check this code when new subtype is added");

   234       // Condition is not a member of this loop?

   235       if( !is_member(phase->get_loop(ctrl)) &&

   236           is_loop_exit(test) )

   237         return true;            // Found reason to peel!

   238     }

   239     // Walk up dominators to loop _head looking for test which is

   240     // executed on every path thru loop.

   241     test = phase->idom(test);

   242   }

   243   return false;

   244 }

   245 

   246 //------------------------------peeled_dom_test_elim---------------------------

   247 // If we got the effect of peeling, either by actually peeling or by making

   248 // a pre-loop which must execute at least once, we can remove all

   249 // loop-invariant dominated tests in the main body.

   250 void PhaseIdealLoop::peeled_dom_test_elim( IdealLoopTree *loop, Node_List &old_new ) {

   251   bool progress = true;

   252   while( progress ) {

   253     progress = false;           // Reset for next iteration

   254     Node *prev = loop->_head->in(LoopNode::LoopBackControl);//loop->tail();

   255     Node *test = prev->in(0);

   256     while( test != loop->_head ) { // Scan till run off top of loop

   257 

   258       int p_op = prev->Opcode();

   259       if( (p_op == Op_IfFalse || p_op == Op_IfTrue) &&

   260           test->is_If() &&      // Test?

   261           !test->in(1)->is_Con() && // And not already obvious?

   262           // Condition is not a member of this loop?

   263           !loop->is_member(get_loop(get_ctrl(test->in(1))))){

   264         // Walk loop body looking for instances of this test

   265         for( uint i = 0; i < loop->_body.size(); i++ ) {

   266           Node *n = loop->_body.at(i);

   267           if( n->is_If() && n->in(1) == test->in(1) /*&& n != loop->tail()->in(0)*/ ) {

   268             // IfNode was dominated by version in peeled loop body

   269             progress = true;

   270             dominated_by( old_new[prev->_idx], n );

   271           }

   272         }

   273       }

   274       prev = test;

   275       test = idom(test);

   276     } // End of scan tests in loop

   277 

   278   } // End of while( progress )

   279 }

   280 

   281 //------------------------------do_peeling-------------------------------------

   282 // Peel the first iteration of the given loop.

   283 // Step 1: Clone the loop body.  The clone becomes the peeled iteration.

   284 //         The pre-loop illegally has 2 control users (old & new loops).

   285 // Step 2: Make the old-loop fall-in edges point to the peeled iteration.

   286 //         Do this by making the old-loop fall-in edges act as if they came

   287 //         around the loopback from the prior iteration (follow the old-loop

   288 //         backedges) and then map to the new peeled iteration.  This leaves

   289 //         the pre-loop with only 1 user (the new peeled iteration), but the

   290 //         peeled-loop backedge has 2 users.

   291 // Step 3: Cut the backedge on the clone (so its not a loop) and remove the

   292 //         extra backedge user.

   293 void PhaseIdealLoop::do_peeling( IdealLoopTree *loop, Node_List &old_new ) {

   294 

   295   C->set_major_progress();

   296   // Peeling a 'main' loop in a pre/main/post situation obfuscates the

   297   // 'pre' loop from the main and the 'pre' can no longer have it's

   298   // iterations adjusted.  Therefore, we need to declare this loop as

   299   // no longer a 'main' loop; it will need new pre and post loops before

   300   // we can do further RCE.

   301   Node *h = loop->_head;

   302   if( h->is_CountedLoop() ) {

   303     CountedLoopNode *cl = h->as_CountedLoop();

   304     assert(cl->trip_count() > 0, "peeling a fully unrolled loop");

   305     cl->set_trip_count(cl->trip_count() - 1);

   306     if( cl->is_main_loop() ) {

   307       cl->set_normal_loop();

   308 #ifndef PRODUCT

   309       if( PrintOpto && VerifyLoopOptimizations ) {

   310         tty->print("Peeling a 'main' loop; resetting to 'normal' ");

   311         loop->dump_head();

   312       }

   313 #endif

   314     }

   315   }

   316 

   317   // Step 1: Clone the loop body.  The clone becomes the peeled iteration.

   318   //         The pre-loop illegally has 2 control users (old & new loops).

   319   clone_loop( loop, old_new, dom_depth(loop->_head) );

   320 

   321 

   322   // Step 2: Make the old-loop fall-in edges point to the peeled iteration.

   323   //         Do this by making the old-loop fall-in edges act as if they came

   324   //         around the loopback from the prior iteration (follow the old-loop

   325   //         backedges) and then map to the new peeled iteration.  This leaves

   326   //         the pre-loop with only 1 user (the new peeled iteration), but the

   327   //         peeled-loop backedge has 2 users.

   328   for (DUIterator_Fast jmax, j = loop->_head->fast_outs(jmax); j < jmax; j++) {

   329     Node* old = loop->_head->fast_out(j);

   330     if( old->in(0) == loop->_head && old->req() == 3 &&

   331         (old->is_Loop() || old->is_Phi()) ) {

   332       Node *new_exit_value = old_new[old->in(LoopNode::LoopBackControl)->_idx];

   333       if( !new_exit_value )     // Backedge value is ALSO loop invariant?

   334         // Then loop body backedge value remains the same.

   335         new_exit_value = old->in(LoopNode::LoopBackControl);

   336       _igvn.hash_delete(old);

   337       old->set_req(LoopNode::EntryControl, new_exit_value);

   338     }

   339   }

   340 

   341 

   342   // Step 3: Cut the backedge on the clone (so its not a loop) and remove the

   343   //         extra backedge user.

   344   Node *nnn = old_new[loop->_head->_idx];

   345   _igvn.hash_delete(nnn);

   346   nnn->set_req(LoopNode::LoopBackControl, C->top());

   347   for (DUIterator_Fast j2max, j2 = nnn->fast_outs(j2max); j2 < j2max; j2++) {

   348     Node* use = nnn->fast_out(j2);

   349     if( use->in(0) == nnn && use->req() == 3 && use->is_Phi() ) {

   350       _igvn.hash_delete(use);

   351       use->set_req(LoopNode::LoopBackControl, C->top());

   352     }

   353   }

   354 

   355 

   356   // Step 4: Correct dom-depth info.  Set to loop-head depth.

   357   int dd = dom_depth(loop->_head);

   358   set_idom(loop->_head, loop->_head->in(1), dd);

   359   for (uint j3 = 0; j3 < loop->_body.size(); j3++) {

   360     Node *old = loop->_body.at(j3);

   361     Node *nnn = old_new[old->_idx];

   362     if (!has_ctrl(nnn))

   363       set_idom(nnn, idom(nnn), dd-1);

   364     // While we're at it, remove any SafePoints from the peeled code

   365     if( old->Opcode() == Op_SafePoint ) {

   366       Node *nnn = old_new[old->_idx];

   367       lazy_replace(nnn,nnn->in(TypeFunc::Control));

   368     }

   369   }

   370 

   371   // Now force out all loop-invariant dominating tests.  The optimizer

   372   // finds some, but we _know_ they are all useless.

   373   peeled_dom_test_elim(loop,old_new);

   374 

   375   loop->record_for_igvn();

   376 }

   377 

   378 //------------------------------policy_maximally_unroll------------------------

   379 // Return exact loop trip count, or 0 if not maximally unrolling

   380 bool IdealLoopTree::policy_maximally_unroll( PhaseIdealLoop *phase ) const {

   381   CountedLoopNode *cl = _head->as_CountedLoop();

   382   assert( cl->is_normal_loop(), "" );

   383 

   384   Node *init_n = cl->init_trip();

   385   Node *limit_n = cl->limit();

   386 

   387   // Non-constant bounds

   388   if( init_n   == NULL || !init_n->is_Con()  ||

   389       limit_n  == NULL || !limit_n->is_Con() ||

   390       // protect against stride not being a constant

   391       !cl->stride_is_con() ) {

   392     return false;

   393   }

   394   int init   = init_n->get_int();

   395   int limit  = limit_n->get_int();

   396   int span   = limit - init;

   397   int stride = cl->stride_con();

   398 

   399   if (init >= limit || stride > span) {

   400     // return a false (no maximally unroll) and the regular unroll/peel

   401     // route will make a small mess which CCP will fold away.

   402     return false;

   403   }

   404   uint trip_count = span/stride;   // trip_count can be greater than 2 Gig.

   405   assert( (int)trip_count*stride == span, "must divide evenly" );

   406 

   407   // Real policy: if we maximally unroll, does it get too big?

   408   // Allow the unrolled mess to get larger than standard loop

   409   // size.  After all, it will no longer be a loop.

   410   uint body_size    = _body.size();

   411   uint unroll_limit = (uint)LoopUnrollLimit * 4;

   412   assert( (intx)unroll_limit == LoopUnrollLimit * 4, "LoopUnrollLimit must fit in 32bits");

   413   cl->set_trip_count(trip_count);

   414   if( trip_count <= unroll_limit && body_size <= unroll_limit ) {

   415     uint new_body_size = body_size * trip_count;

   416     if (new_body_size <= unroll_limit &&

   417         body_size == new_body_size / trip_count &&

   418         // Unrolling can result in a large amount of node construction

   419         new_body_size < MaxNodeLimit - phase->C->unique()) {

   420       return true;    // maximally unroll

   421     }

   422   }

   423 

   424   return false;               // Do not maximally unroll

   425 }

   426 

   427 

   428 //------------------------------policy_unroll----------------------------------

   429 // Return TRUE or FALSE if the loop should be unrolled or not.  Unroll if

   430 // the loop is a CountedLoop and the body is small enough.

   431 bool IdealLoopTree::policy_unroll( PhaseIdealLoop *phase ) const {

   432 

   433   CountedLoopNode *cl = _head->as_CountedLoop();

   434   assert( cl->is_normal_loop() || cl->is_main_loop(), "" );

   435 

   436   // protect against stride not being a constant

   437   if( !cl->stride_is_con() ) return false;

   438 

   439   // protect against over-unrolling

   440   if( cl->trip_count() <= 1 ) return false;

   441 

   442   int future_unroll_ct = cl->unrolled_count() * 2;

   443 

   444   // Don't unroll if the next round of unrolling would push us

   445   // over the expected trip count of the loop.  One is subtracted

   446   // from the expected trip count because the pre-loop normally

   447   // executes 1 iteration.

   448   if (UnrollLimitForProfileCheck > 0 &&

   449       cl->profile_trip_cnt() != COUNT_UNKNOWN &&

   450       future_unroll_ct        > UnrollLimitForProfileCheck &&

   451       (float)future_unroll_ct > cl->profile_trip_cnt() - 1.0) {

   452     return false;

   453   }

   454 

   455   // When unroll count is greater than LoopUnrollMin, don't unroll if:

   456   //   the residual iterations are more than 10% of the trip count

   457   //   and rounds of "unroll,optimize" are not making significant progress

   458   //   Progress defined as current size less than 20% larger than previous size.

   459   if (UseSuperWord && cl->node_count_before_unroll() > 0 &&

   460       future_unroll_ct > LoopUnrollMin &&

   461       (future_unroll_ct - 1) * 10.0 > cl->profile_trip_cnt() &&

   462       1.2 * cl->node_count_before_unroll() < (double)_body.size()) {

   463     return false;

   464   }

   465 

   466   Node *init_n = cl->init_trip();

   467   Node *limit_n = cl->limit();

   468   // Non-constant bounds.

   469   // Protect against over-unrolling when init or/and limit are not constant

   470   // (so that trip_count's init value is maxint) but iv range is known.

   471   if( init_n   == NULL || !init_n->is_Con()  ||

   472       limit_n  == NULL || !limit_n->is_Con() ) {

   473     Node* phi = cl->phi();

   474     if( phi != NULL ) {

   475       assert(phi->is_Phi() && phi->in(0) == _head, "Counted loop should have iv phi.");

   476       const TypeInt* iv_type = phase->_igvn.type(phi)->is_int();

   477       int next_stride = cl->stride_con() * 2; // stride after this unroll

   478       if( next_stride > 0 ) {

   479         if( iv_type->_lo + next_stride <= iv_type->_lo || // overflow

   480             iv_type->_lo + next_stride >  iv_type->_hi ) {

   481           return false;  // over-unrolling

   482         }

   483       } else if( next_stride < 0 ) {

   484         if( iv_type->_hi + next_stride >= iv_type->_hi || // overflow

   485             iv_type->_hi + next_stride <  iv_type->_lo ) {

   486           return false;  // over-unrolling

   487         }

   488       }

   489     }

   490   }

   491 

   492   // Adjust body_size to determine if we unroll or not

   493   uint body_size = _body.size();

   494   // Key test to unroll CaffeineMark's Logic test

   495   int xors_in_loop = 0;

   496   // Also count ModL, DivL and MulL which expand mightly

   497   for( uint k = 0; k < _body.size(); k++ ) {

   498     switch( _body.at(k)->Opcode() ) {

   499     case Op_XorI: xors_in_loop++; break; // CaffeineMark's Logic test

   500     case Op_ModL: body_size += 30; break;

   501     case Op_DivL: body_size += 30; break;

   502     case Op_MulL: body_size += 10; break;

   503     }

   504   }

   505 

   506   // Check for being too big

   507   if( body_size > (uint)LoopUnrollLimit ) {

   508     if( xors_in_loop >= 4 && body_size < (uint)LoopUnrollLimit*4) return true;

   509     // Normal case: loop too big

   510     return false;

   511   }

   512 

   513   // Check for stride being a small enough constant

   514   if( abs(cl->stride_con()) > (1<<3) ) return false;

   515 

   516   // Unroll once!  (Each trip will soon do double iterations)

   517   return true;

   518 }

   519 

   520 //------------------------------policy_align-----------------------------------

   521 // Return TRUE or FALSE if the loop should be cache-line aligned.  Gather the

   522 // expression that does the alignment.  Note that only one array base can be

   523 // aligned in a loop (unless the VM guarentees mutual alignment).  Note that

   524 // if we vectorize short memory ops into longer memory ops, we may want to

   525 // increase alignment.

   526 bool IdealLoopTree::policy_align( PhaseIdealLoop *phase ) const {

   527   return false;

   528 }

   529 

   530 //------------------------------policy_range_check-----------------------------

   531 // Return TRUE or FALSE if the loop should be range-check-eliminated.

   532 // Actually we do iteration-splitting, a more powerful form of RCE.

   533 bool IdealLoopTree::policy_range_check( PhaseIdealLoop *phase ) const {

   534   if( !RangeCheckElimination ) return false;

   535 

   536   CountedLoopNode *cl = _head->as_CountedLoop();

   537   // If we unrolled with no intention of doing RCE and we later

   538   // changed our minds, we got no pre-loop.  Either we need to

   539   // make a new pre-loop, or we gotta disallow RCE.

   540   if( cl->is_main_no_pre_loop() ) return false; // Disallowed for now.

   541   Node *trip_counter = cl->phi();

   542 

   543   // Check loop body for tests of trip-counter plus loop-invariant vs

   544   // loop-invariant.

   545   for( uint i = 0; i < _body.size(); i++ ) {

   546     Node *iff = _body[i];

   547     if( iff->Opcode() == Op_If ) { // Test?

   548 

   549       // Comparing trip+off vs limit

   550       Node *bol = iff->in(1);

   551       if( bol->req() != 2 ) continue; // dead constant test

   552       Node *cmp = bol->in(1);

   553 

   554       Node *rc_exp = cmp->in(1);

   555       Node *limit = cmp->in(2);

   556 

   557       Node *limit_c = phase->get_ctrl(limit);

   558       if( limit_c == phase->C->top() )

   559         return false;           // Found dead test on live IF?  No RCE!

   560       if( is_member(phase->get_loop(limit_c) ) ) {

   561         // Compare might have operands swapped; commute them

   562         rc_exp = cmp->in(2);

   563         limit  = cmp->in(1);

   564         limit_c = phase->get_ctrl(limit);

   565         if( is_member(phase->get_loop(limit_c) ) )

   566           continue;             // Both inputs are loop varying; cannot RCE

   567       }

   568 

   569       if (!phase->is_scaled_iv_plus_offset(rc_exp, trip_counter, NULL, NULL)) {

   570         continue;

   571       }

   572       // Yeah!  Found a test like 'trip+off vs limit'

   573       // Test is an IfNode, has 2 projections.  If BOTH are in the loop

   574       // we need loop unswitching instead of iteration splitting.

   575       if( is_loop_exit(iff) )

   576         return true;            // Found reason to split iterations

   577     } // End of is IF

   578   }

   579 

   580   return false;

   581 }

   582 

   583 //------------------------------policy_peel_only-------------------------------

   584 // Return TRUE or FALSE if the loop should NEVER be RCE'd or aligned.  Useful

   585 // for unrolling loops with NO array accesses.

   586 bool IdealLoopTree::policy_peel_only( PhaseIdealLoop *phase ) const {

   587 

   588   for( uint i = 0; i < _body.size(); i++ )

   589     if( _body[i]->is_Mem() )

   590       return false;

   591 

   592   // No memory accesses at all!

   593   return true;

   594 }

   595 

   596 //------------------------------clone_up_backedge_goo--------------------------

   597 // If Node n lives in the back_ctrl block and cannot float, we clone a private

   598 // version of n in preheader_ctrl block and return that, otherwise return n.

   599 Node *PhaseIdealLoop::clone_up_backedge_goo( Node *back_ctrl, Node *preheader_ctrl, Node *n ) {

   600   if( get_ctrl(n) != back_ctrl ) return n;

   601 

   602   Node *x = NULL;               // If required, a clone of 'n'

   603   // Check for 'n' being pinned in the backedge.

   604   if( n->in(0) && n->in(0) == back_ctrl ) {

   605     x = n->clone();             // Clone a copy of 'n' to preheader

   606     x->set_req( 0, preheader_ctrl ); // Fix x's control input to preheader

   607   }

   608 

   609   // Recursive fixup any other input edges into x.

   610   // If there are no changes we can just return 'n', otherwise

   611   // we need to clone a private copy and change it.

   612   for( uint i = 1; i < n->req(); i++ ) {

   613     Node *g = clone_up_backedge_goo( back_ctrl, preheader_ctrl, n->in(i) );

   614     if( g != n->in(i) ) {

   615       if( !x )

   616         x = n->clone();

   617       x->set_req(i, g);

   618     }

   619   }

   620   if( x ) {                     // x can legally float to pre-header location

   621     register_new_node( x, preheader_ctrl );

   622     return x;

   623   } else {                      // raise n to cover LCA of uses

   624     set_ctrl( n, find_non_split_ctrl(back_ctrl->in(0)) );

   625   }

   626   return n;

   627 }

   628 

   629 //------------------------------insert_pre_post_loops--------------------------

   630 // Insert pre and post loops.  If peel_only is set, the pre-loop can not have

   631 // more iterations added.  It acts as a 'peel' only, no lower-bound RCE, no

   632 // alignment.  Useful to unroll loops that do no array accesses.

   633 void PhaseIdealLoop::insert_pre_post_loops( IdealLoopTree *loop, Node_List &old_new, bool peel_only ) {

   634 

   635   C->set_major_progress();

   636 

   637   // Find common pieces of the loop being guarded with pre & post loops

   638   CountedLoopNode *main_head = loop->_head->as_CountedLoop();

   639   assert( main_head->is_normal_loop(), "" );

   640   CountedLoopEndNode *main_end = main_head->loopexit();

   641   assert( main_end->outcnt() == 2, "1 true, 1 false path only" );

   642   uint dd_main_head = dom_depth(main_head);

   643   uint max = main_head->outcnt();

   644 

   645   Node *pre_header= main_head->in(LoopNode::EntryControl);

   646   Node *init      = main_head->init_trip();

   647   Node *incr      = main_end ->incr();

   648   Node *limit     = main_end ->limit();

   649   Node *stride    = main_end ->stride();

   650   Node *cmp       = main_end ->cmp_node();

   651   BoolTest::mask b_test = main_end->test_trip();

   652 

   653   // Need only 1 user of 'bol' because I will be hacking the loop bounds.

   654   Node *bol = main_end->in(CountedLoopEndNode::TestValue);

   655   if( bol->outcnt() != 1 ) {

   656     bol = bol->clone();

   657     register_new_node(bol,main_end->in(CountedLoopEndNode::TestControl));

   658     _igvn.hash_delete(main_end);

   659     main_end->set_req(CountedLoopEndNode::TestValue, bol);

   660   }

   661   // Need only 1 user of 'cmp' because I will be hacking the loop bounds.

   662   if( cmp->outcnt() != 1 ) {

   663     cmp = cmp->clone();

   664     register_new_node(cmp,main_end->in(CountedLoopEndNode::TestControl));

   665     _igvn.hash_delete(bol);

   666     bol->set_req(1, cmp);

   667   }

   668 

   669   //------------------------------

   670   // Step A: Create Post-Loop.

   671   Node* main_exit = main_end->proj_out(false);

   672   assert( main_exit->Opcode() == Op_IfFalse, "" );

   673   int dd_main_exit = dom_depth(main_exit);

   674 

   675   // Step A1: Clone the loop body.  The clone becomes the post-loop.  The main

   676   // loop pre-header illegally has 2 control users (old & new loops).

   677   clone_loop( loop, old_new, dd_main_exit );

   678   assert( old_new[main_end ->_idx]->Opcode() == Op_CountedLoopEnd, "" );

   679   CountedLoopNode *post_head = old_new[main_head->_idx]->as_CountedLoop();

   680   post_head->set_post_loop(main_head);

   681 

   682   // Build the main-loop normal exit.

   683   IfFalseNode *new_main_exit = new (C, 1) IfFalseNode(main_end);

   684   _igvn.register_new_node_with_optimizer( new_main_exit );

   685   set_idom(new_main_exit, main_end, dd_main_exit );

   686   set_loop(new_main_exit, loop->_parent);

   687 

   688   // Step A2: Build a zero-trip guard for the post-loop.  After leaving the

   689   // main-loop, the post-loop may not execute at all.  We 'opaque' the incr

   690   // (the main-loop trip-counter exit value) because we will be changing

   691   // the exit value (via unrolling) so we cannot constant-fold away the zero

   692   // trip guard until all unrolling is done.

   693   Node *zer_opaq = new (C, 2) Opaque1Node(incr);

   694   Node *zer_cmp  = new (C, 3) CmpINode( zer_opaq, limit );

   695   Node *zer_bol  = new (C, 2) BoolNode( zer_cmp, b_test );

   696   register_new_node( zer_opaq, new_main_exit );

   697   register_new_node( zer_cmp , new_main_exit );

   698   register_new_node( zer_bol , new_main_exit );

   699 

   700   // Build the IfNode

   701   IfNode *zer_iff = new (C, 2) IfNode( new_main_exit, zer_bol, PROB_FAIR, COUNT_UNKNOWN );

   702   _igvn.register_new_node_with_optimizer( zer_iff );

   703   set_idom(zer_iff, new_main_exit, dd_main_exit);

   704   set_loop(zer_iff, loop->_parent);

   705 

   706   // Plug in the false-path, taken if we need to skip post-loop

   707   _igvn.hash_delete( main_exit );

   708   main_exit->set_req(0, zer_iff);

   709   _igvn._worklist.push(main_exit);

   710   set_idom(main_exit, zer_iff, dd_main_exit);

   711   set_idom(main_exit->unique_out(), zer_iff, dd_main_exit);

   712   // Make the true-path, must enter the post loop

   713   Node *zer_taken = new (C, 1) IfTrueNode( zer_iff );

   714   _igvn.register_new_node_with_optimizer( zer_taken );

   715   set_idom(zer_taken, zer_iff, dd_main_exit);

   716   set_loop(zer_taken, loop->_parent);

   717   // Plug in the true path

   718   _igvn.hash_delete( post_head );

   719   post_head->set_req(LoopNode::EntryControl, zer_taken);

   720   set_idom(post_head, zer_taken, dd_main_exit);

   721 

   722   // Step A3: Make the fall-in values to the post-loop come from the

   723   // fall-out values of the main-loop.

   724   for (DUIterator_Fast imax, i = main_head->fast_outs(imax); i < imax; i++) {

   725     Node* main_phi = main_head->fast_out(i);

   726     if( main_phi->is_Phi() && main_phi->in(0) == main_head && main_phi->outcnt() >0 ) {

   727       Node *post_phi = old_new[main_phi->_idx];

   728       Node *fallmain  = clone_up_backedge_goo(main_head->back_control(),

   729                                               post_head->init_control(),

   730                                               main_phi->in(LoopNode::LoopBackControl));

   731       _igvn.hash_delete(post_phi);

   732       post_phi->set_req( LoopNode::EntryControl, fallmain );

   733     }

   734   }

   735 

   736   // Update local caches for next stanza

   737   main_exit = new_main_exit;

   738 

   739 

   740   //------------------------------

   741   // Step B: Create Pre-Loop.

   742 

   743   // Step B1: Clone the loop body.  The clone becomes the pre-loop.  The main

   744   // loop pre-header illegally has 2 control users (old & new loops).

   745   clone_loop( loop, old_new, dd_main_head );

   746   CountedLoopNode*    pre_head = old_new[main_head->_idx]->as_CountedLoop();

   747   CountedLoopEndNode* pre_end  = old_new[main_end ->_idx]->as_CountedLoopEnd();

   748   pre_head->set_pre_loop(main_head);

   749   Node *pre_incr = old_new[incr->_idx];

   750 

   751   // Find the pre-loop normal exit.

   752   Node* pre_exit = pre_end->proj_out(false);

   753   assert( pre_exit->Opcode() == Op_IfFalse, "" );

   754   IfFalseNode *new_pre_exit = new (C, 1) IfFalseNode(pre_end);

   755   _igvn.register_new_node_with_optimizer( new_pre_exit );

   756   set_idom(new_pre_exit, pre_end, dd_main_head);

   757   set_loop(new_pre_exit, loop->_parent);

   758 

   759   // Step B2: Build a zero-trip guard for the main-loop.  After leaving the

   760   // pre-loop, the main-loop may not execute at all.  Later in life this

   761   // zero-trip guard will become the minimum-trip guard when we unroll

   762   // the main-loop.

   763   Node *min_opaq = new (C, 2) Opaque1Node(limit);

   764   Node *min_cmp  = new (C, 3) CmpINode( pre_incr, min_opaq );

   765   Node *min_bol  = new (C, 2) BoolNode( min_cmp, b_test );

   766   register_new_node( min_opaq, new_pre_exit );

   767   register_new_node( min_cmp , new_pre_exit );

   768   register_new_node( min_bol , new_pre_exit );

   769 

   770   // Build the IfNode

   771   IfNode *min_iff = new (C, 2) IfNode( new_pre_exit, min_bol, PROB_FAIR, COUNT_UNKNOWN );

   772   _igvn.register_new_node_with_optimizer( min_iff );

   773   set_idom(min_iff, new_pre_exit, dd_main_head);

   774   set_loop(min_iff, loop->_parent);

   775 

   776   // Plug in the false-path, taken if we need to skip main-loop

   777   _igvn.hash_delete( pre_exit );

   778   pre_exit->set_req(0, min_iff);

   779   set_idom(pre_exit, min_iff, dd_main_head);

   780   set_idom(pre_exit->unique_out(), min_iff, dd_main_head);

   781   // Make the true-path, must enter the main loop

   782   Node *min_taken = new (C, 1) IfTrueNode( min_iff );

   783   _igvn.register_new_node_with_optimizer( min_taken );

   784   set_idom(min_taken, min_iff, dd_main_head);

   785   set_loop(min_taken, loop->_parent);

   786   // Plug in the true path

   787   _igvn.hash_delete( main_head );

   788   main_head->set_req(LoopNode::EntryControl, min_taken);

   789   set_idom(main_head, min_taken, dd_main_head);

   790 

   791   // Step B3: Make the fall-in values to the main-loop come from the

   792   // fall-out values of the pre-loop.

   793   for (DUIterator_Fast i2max, i2 = main_head->fast_outs(i2max); i2 < i2max; i2++) {

   794     Node* main_phi = main_head->fast_out(i2);

   795     if( main_phi->is_Phi() && main_phi->in(0) == main_head && main_phi->outcnt() > 0 ) {

   796       Node *pre_phi = old_new[main_phi->_idx];

   797       Node *fallpre  = clone_up_backedge_goo(pre_head->back_control(),

   798                                              main_head->init_control(),

   799                                              pre_phi->in(LoopNode::LoopBackControl));

   800       _igvn.hash_delete(main_phi);

   801       main_phi->set_req( LoopNode::EntryControl, fallpre );

   802     }

   803   }

   804 

   805   // Step B4: Shorten the pre-loop to run only 1 iteration (for now).

   806   // RCE and alignment may change this later.

   807   Node *cmp_end = pre_end->cmp_node();

   808   assert( cmp_end->in(2) == limit, "" );

   809   Node *pre_limit = new (C, 3) AddINode( init, stride );

   810 

   811   // Save the original loop limit in this Opaque1 node for

   812   // use by range check elimination.

   813   Node *pre_opaq  = new (C, 3) Opaque1Node(pre_limit, limit);

   814 

   815   register_new_node( pre_limit, pre_head->in(0) );

   816   register_new_node( pre_opaq , pre_head->in(0) );

   817 

   818   // Since no other users of pre-loop compare, I can hack limit directly

   819   assert( cmp_end->outcnt() == 1, "no other users" );

   820   _igvn.hash_delete(cmp_end);

   821   cmp_end->set_req(2, peel_only ? pre_limit : pre_opaq);

   822 

   823   // Special case for not-equal loop bounds:

   824   // Change pre loop test, main loop test, and the

   825   // main loop guard test to use lt or gt depending on stride

   826   // direction:

   827   // positive stride use <

   828   // negative stride use >

   829 

   830   if (pre_end->in(CountedLoopEndNode::TestValue)->as_Bool()->_test._test == BoolTest::ne) {

   831 

   832     BoolTest::mask new_test = (main_end->stride_con() > 0) ? BoolTest::lt : BoolTest::gt;

   833     // Modify pre loop end condition

   834     Node* pre_bol = pre_end->in(CountedLoopEndNode::TestValue)->as_Bool();

   835     BoolNode* new_bol0 = new (C, 2) BoolNode(pre_bol->in(1), new_test);

   836     register_new_node( new_bol0, pre_head->in(0) );

   837     _igvn.hash_delete(pre_end);

   838     pre_end->set_req(CountedLoopEndNode::TestValue, new_bol0);

   839     // Modify main loop guard condition

   840     assert(min_iff->in(CountedLoopEndNode::TestValue) == min_bol, "guard okay");

   841     BoolNode* new_bol1 = new (C, 2) BoolNode(min_bol->in(1), new_test);

   842     register_new_node( new_bol1, new_pre_exit );

   843     _igvn.hash_delete(min_iff);

   844     min_iff->set_req(CountedLoopEndNode::TestValue, new_bol1);

   845     // Modify main loop end condition

   846     BoolNode* main_bol = main_end->in(CountedLoopEndNode::TestValue)->as_Bool();

   847     BoolNode* new_bol2 = new (C, 2) BoolNode(main_bol->in(1), new_test);

   848     register_new_node( new_bol2, main_end->in(CountedLoopEndNode::TestControl) );

   849     _igvn.hash_delete(main_end);

   850     main_end->set_req(CountedLoopEndNode::TestValue, new_bol2);

   851   }

   852 

   853   // Flag main loop

   854   main_head->set_main_loop();

   855   if( peel_only ) main_head->set_main_no_pre_loop();

   856 

   857   // It's difficult to be precise about the trip-counts

   858   // for the pre/post loops.  They are usually very short,

   859   // so guess that 4 trips is a reasonable value.

   860   post_head->set_profile_trip_cnt(4.0);

   861   pre_head->set_profile_trip_cnt(4.0);

   862 

   863   // Now force out all loop-invariant dominating tests.  The optimizer

   864   // finds some, but we _know_ they are all useless.

   865   peeled_dom_test_elim(loop,old_new);

   866 }

   867 

   868 //------------------------------is_invariant-----------------------------

   869 // Return true if n is invariant

   870 bool IdealLoopTree::is_invariant(Node* n) const {

   871   Node *n_c = _phase->get_ctrl(n);

   872   if (n_c->is_top()) return false;

   873   return !is_member(_phase->get_loop(n_c));

   874 }

   875 

   876 

   877 //------------------------------do_unroll--------------------------------------

   878 // Unroll the loop body one step - make each trip do 2 iterations.

   879 void PhaseIdealLoop::do_unroll( IdealLoopTree *loop, Node_List &old_new, bool adjust_min_trip ) {

   880   assert( LoopUnrollLimit, "" );

   881 #ifndef PRODUCT

   882   if( PrintOpto && VerifyLoopOptimizations ) {

   883     tty->print("Unrolling ");

   884     loop->dump_head();

   885   }

   886 #endif

   887   CountedLoopNode *loop_head = loop->_head->as_CountedLoop();

   888   CountedLoopEndNode *loop_end = loop_head->loopexit();

   889   assert( loop_end, "" );

   890 

   891   // Remember loop node count before unrolling to detect

   892   // if rounds of unroll,optimize are making progress

   893   loop_head->set_node_count_before_unroll(loop->_body.size());

   894 

   895   Node *ctrl  = loop_head->in(LoopNode::EntryControl);

   896   Node *limit = loop_head->limit();

   897   Node *init  = loop_head->init_trip();

   898   Node *strid = loop_head->stride();

   899 

   900   Node *opaq = NULL;

   901   if( adjust_min_trip ) {       // If not maximally unrolling, need adjustment

   902     assert( loop_head->is_main_loop(), "" );

   903     assert( ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "" );

   904     Node *iff = ctrl->in(0);

   905     assert( iff->Opcode() == Op_If, "" );

   906     Node *bol = iff->in(1);

   907     assert( bol->Opcode() == Op_Bool, "" );

   908     Node *cmp = bol->in(1);

   909     assert( cmp->Opcode() == Op_CmpI, "" );

   910     opaq = cmp->in(2);

   911     // Occasionally it's possible for a pre-loop Opaque1 node to be

   912     // optimized away and then another round of loop opts attempted.

   913     // We can not optimize this particular loop in that case.

   914     if( opaq->Opcode() != Op_Opaque1 )

   915       return;                   // Cannot find pre-loop!  Bail out!

   916   }

   917 

   918   C->set_major_progress();

   919 

   920   // Adjust max trip count. The trip count is intentionally rounded

   921   // down here (e.g. 15-> 7-> 3-> 1) because if we unwittingly over-unroll,

   922   // the main, unrolled, part of the loop will never execute as it is protected

   923   // by the min-trip test.  See bug 4834191 for a case where we over-unrolled

   924   // and later determined that part of the unrolled loop was dead.

   925   loop_head->set_trip_count(loop_head->trip_count() / 2);

   926 

   927   // Double the count of original iterations in the unrolled loop body.

   928   loop_head->double_unrolled_count();

   929 

   930   // -----------

   931   // Step 2: Cut back the trip counter for an unroll amount of 2.

   932   // Loop will normally trip (limit - init)/stride_con.  Since it's a

   933   // CountedLoop this is exact (stride divides limit-init exactly).

   934   // We are going to double the loop body, so we want to knock off any

   935   // odd iteration: (trip_cnt & ~1).  Then back compute a new limit.

   936   Node *span = new (C, 3) SubINode( limit, init );

   937   register_new_node( span, ctrl );

   938   Node *trip = new (C, 3) DivINode( 0, span, strid );

   939   register_new_node( trip, ctrl );

   940   Node *mtwo = _igvn.intcon(-2);

   941   set_ctrl(mtwo, C->root());

   942   Node *rond = new (C, 3) AndINode( trip, mtwo );

   943   register_new_node( rond, ctrl );

   944   Node *spn2 = new (C, 3) MulINode( rond, strid );

   945   register_new_node( spn2, ctrl );

   946   Node *lim2 = new (C, 3) AddINode( spn2, init );

   947   register_new_node( lim2, ctrl );

   948 

   949   // Hammer in the new limit

   950   Node *ctrl2 = loop_end->in(0);

   951   Node *cmp2 = new (C, 3) CmpINode( loop_head->incr(), lim2 );

   952   register_new_node( cmp2, ctrl2 );

   953   Node *bol2 = new (C, 2) BoolNode( cmp2, loop_end->test_trip() );

   954   register_new_node( bol2, ctrl2 );

   955   _igvn.hash_delete(loop_end);

   956   loop_end->set_req(CountedLoopEndNode::TestValue, bol2);

   957 

   958   // Step 3: Find the min-trip test guaranteed before a 'main' loop.

   959   // Make it a 1-trip test (means at least 2 trips).

   960   if( adjust_min_trip ) {

   961     // Guard test uses an 'opaque' node which is not shared.  Hence I

   962     // can edit it's inputs directly.  Hammer in the new limit for the

   963     // minimum-trip guard.

   964     assert( opaq->outcnt() == 1, "" );

   965     _igvn.hash_delete(opaq);

   966     opaq->set_req(1, lim2);

   967   }

   968 

   969   // ---------

   970   // Step 4: Clone the loop body.  Move it inside the loop.  This loop body

   971   // represents the odd iterations; since the loop trips an even number of

   972   // times its backedge is never taken.  Kill the backedge.

   973   uint dd = dom_depth(loop_head);

   974   clone_loop( loop, old_new, dd );

   975 

   976   // Make backedges of the clone equal to backedges of the original.

   977   // Make the fall-in from the original come from the fall-out of the clone.

   978   for (DUIterator_Fast jmax, j = loop_head->fast_outs(jmax); j < jmax; j++) {

   979     Node* phi = loop_head->fast_out(j);

   980     if( phi->is_Phi() && phi->in(0) == loop_head && phi->outcnt() > 0 ) {

   981       Node *newphi = old_new[phi->_idx];

   982       _igvn.hash_delete( phi );

   983       _igvn.hash_delete( newphi );

   984 

   985       phi   ->set_req(LoopNode::   EntryControl, newphi->in(LoopNode::LoopBackControl));

   986       newphi->set_req(LoopNode::LoopBackControl, phi   ->in(LoopNode::LoopBackControl));

   987       phi   ->set_req(LoopNode::LoopBackControl, C->top());

   988     }

   989   }

   990   Node *clone_head = old_new[loop_head->_idx];

   991   _igvn.hash_delete( clone_head );

   992   loop_head ->set_req(LoopNode::   EntryControl, clone_head->in(LoopNode::LoopBackControl));

   993   clone_head->set_req(LoopNode::LoopBackControl, loop_head ->in(LoopNode::LoopBackControl));

   994   loop_head ->set_req(LoopNode::LoopBackControl, C->top());

   995   loop->_head = clone_head;     // New loop header

   996 

   997   set_idom(loop_head,  loop_head ->in(LoopNode::EntryControl), dd);

   998   set_idom(clone_head, clone_head->in(LoopNode::EntryControl), dd);

   999 

  1000   // Kill the clone's backedge

  1001   Node *newcle = old_new[loop_end->_idx];

  1002   _igvn.hash_delete( newcle );

  1003   Node *one = _igvn.intcon(1);

  1004   set_ctrl(one, C->root());

  1005   newcle->set_req(1, one);

  1006   // Force clone into same loop body

  1007   uint max = loop->_body.size();

  1008   for( uint k = 0; k < max; k++ ) {

  1009     Node *old = loop->_body.at(k);

  1010     Node *nnn = old_new[old->_idx];

  1011     loop->_body.push(nnn);

  1012     if (!has_ctrl(old))

  1013       set_loop(nnn, loop);

  1014   }

  1015 }

  1016 

  1017 //------------------------------do_maximally_unroll----------------------------

  1018 

  1019 void PhaseIdealLoop::do_maximally_unroll( IdealLoopTree *loop, Node_List &old_new ) {

  1020   CountedLoopNode *cl = loop->_head->as_CountedLoop();

  1021   assert( cl->trip_count() > 0, "");

  1022 

  1023   // If loop is tripping an odd number of times, peel odd iteration

  1024   if( (cl->trip_count() & 1) == 1 ) {

  1025     do_peeling( loop, old_new );

  1026   }

  1027 

  1028   // Now its tripping an even number of times remaining.  Double loop body.

  1029   // Do not adjust pre-guards; they are not needed and do not exist.

  1030   if( cl->trip_count() > 0 ) {

  1031     do_unroll( loop, old_new, false );

  1032   }

  1033 }

  1034 

  1035 //------------------------------dominates_backedge---------------------------------

  1036 // Returns true if ctrl is executed on every complete iteration

  1037 bool IdealLoopTree::dominates_backedge(Node* ctrl) {

  1038   assert(ctrl->is_CFG(), "must be control");

  1039   Node* backedge = _head->as_Loop()->in(LoopNode::LoopBackControl);

  1040   return _phase->dom_lca_internal(ctrl, backedge) == ctrl;

  1041 }

  1042 

  1043 //------------------------------add_constraint---------------------------------

  1044 // Constrain the main loop iterations so the condition:

  1045 //    scale_con * I + offset  <  limit

  1046 // always holds true.  That is, either increase the number of iterations in

  1047 // the pre-loop or the post-loop until the condition holds true in the main

  1048 // loop.  Stride, scale, offset and limit are all loop invariant.  Further,

  1049 // stride and scale are constants (offset and limit often are).

  1050 void PhaseIdealLoop::add_constraint( int stride_con, int scale_con, Node *offset, Node *limit, Node *pre_ctrl, Node **pre_limit, Node **main_limit ) {

  1051 

  1052   // Compute "I :: (limit-offset)/scale_con"

  1053   Node *con = new (C, 3) SubINode( limit, offset );

  1054   register_new_node( con, pre_ctrl );

  1055   Node *scale = _igvn.intcon(scale_con);

  1056   set_ctrl(scale, C->root());

  1057   Node *X = new (C, 3) DivINode( 0, con, scale );

  1058   register_new_node( X, pre_ctrl );

  1059 

  1060   // For positive stride, the pre-loop limit always uses a MAX function

  1061   // and the main loop a MIN function.  For negative stride these are

  1062   // reversed.

  1063 

  1064   // Also for positive stride*scale the affine function is increasing, so the

  1065   // pre-loop must check for underflow and the post-loop for overflow.

  1066   // Negative stride*scale reverses this; pre-loop checks for overflow and

  1067   // post-loop for underflow.

  1068   if( stride_con*scale_con > 0 ) {

  1069     // Compute I < (limit-offset)/scale_con

  1070     // Adjust main-loop last iteration to be MIN/MAX(main_loop,X)

  1071     *main_limit = (stride_con > 0)

  1072       ? (Node*)(new (C, 3) MinINode( *main_limit, X ))

  1073       : (Node*)(new (C, 3) MaxINode( *main_limit, X ));

  1074     register_new_node( *main_limit, pre_ctrl );

  1075 

  1076   } else {

  1077     // Compute (limit-offset)/scale_con + SGN(-scale_con) <= I

  1078     // Add the negation of the main-loop constraint to the pre-loop.

  1079     // See footnote [++] below for a derivation of the limit expression.

  1080     Node *incr = _igvn.intcon(scale_con > 0 ? -1 : 1);

  1081     set_ctrl(incr, C->root());

  1082     Node *adj = new (C, 3) AddINode( X, incr );

  1083     register_new_node( adj, pre_ctrl );

  1084     *pre_limit = (scale_con > 0)

  1085       ? (Node*)new (C, 3) MinINode( *pre_limit, adj )

  1086       : (Node*)new (C, 3) MaxINode( *pre_limit, adj );

  1087     register_new_node( *pre_limit, pre_ctrl );

  1088 

  1089 //   [++] Here's the algebra that justifies the pre-loop limit expression:

  1090 //

  1091 //   NOT( scale_con * I + offset  <  limit )

  1092 //      ==

  1093 //   scale_con * I + offset  >=  limit

  1094 //      ==

  1095 //   SGN(scale_con) * I  >=  (limit-offset)/|scale_con|

  1096 //      ==

  1097 //   (limit-offset)/|scale_con|   <=  I * SGN(scale_con)

  1098 //      ==

  1099 //   (limit-offset)/|scale_con|-1  <  I * SGN(scale_con)

  1100 //      ==

  1101 //   ( if (scale_con > 0) /*common case*/

  1102 //       (limit-offset)/scale_con - 1  <  I

  1103 //     else

  1104 //       (limit-offset)/scale_con + 1  >  I

  1105 //    )

  1106 //   ( if (scale_con > 0) /*common case*/

  1107 //       (limit-offset)/scale_con + SGN(-scale_con)  <  I

  1108 //     else

  1109 //       (limit-offset)/scale_con + SGN(-scale_con)  >  I

  1110   }

  1111 }

  1112 

  1113 

  1114 //------------------------------is_scaled_iv---------------------------------

  1115 // Return true if exp is a constant times an induction var

  1116 bool PhaseIdealLoop::is_scaled_iv(Node* exp, Node* iv, int* p_scale) {

  1117   if (exp == iv) {

  1118     if (p_scale != NULL) {

  1119       *p_scale = 1;

  1120     }

  1121     return true;

  1122   }

  1123   int opc = exp->Opcode();

  1124   if (opc == Op_MulI) {

  1125     if (exp->in(1) == iv && exp->in(2)->is_Con()) {

  1126       if (p_scale != NULL) {

  1127         *p_scale = exp->in(2)->get_int();

  1128       }

  1129       return true;

  1130     }

  1131     if (exp->in(2) == iv && exp->in(1)->is_Con()) {

  1132       if (p_scale != NULL) {

  1133         *p_scale = exp->in(1)->get_int();

  1134       }

  1135       return true;