< prev index next >

src/hotspot/share/opto/loopTransform.cpp

Print this page




 118     int stride_con = cl->stride_con();
 119     jlong init_con = phase->_igvn.type(init_n)->is_int()->_lo;
 120     jlong limit_con = phase->_igvn.type(limit_n)->is_int()->_hi;
 121     int stride_m   = stride_con - (stride_con > 0 ? 1 : -1);
 122     jlong trip_count = (limit_con - init_con + stride_m)/stride_con;
 123     if (trip_count > 0 && (julong)trip_count < (julong)max_juint) {
 124       if (init_n->is_Con() && limit_n->is_Con()) {
 125         // Set exact trip count.
 126         cl->set_exact_trip_count((uint)trip_count);
 127       } else if (cl->unrolled_count() == 1) {
 128         // Set maximum trip count before unrolling.
 129         cl->set_trip_count((uint)trip_count);
 130       }
 131     }
 132   }
 133 }
 134 
 135 //------------------------------compute_profile_trip_cnt----------------------------
 136 // Compute loop trip count from profile data as
 137 //    (backedge_count + loop_exit_count) / loop_exit_count
 138 void IdealLoopTree::compute_profile_trip_cnt( PhaseIdealLoop *phase ) {
 139   if (!_head->is_CountedLoop()) {


































 140     return;
 141   }
 142   CountedLoopNode* head = _head->as_CountedLoop();
 143   if (head->profile_trip_cnt() != COUNT_UNKNOWN) {
 144     return; // Already computed
 145   }
 146   float trip_cnt = (float)max_jint; // default is big
 147 
 148   Node* back = head->in(LoopNode::LoopBackControl);
 149   while (back != head) {
 150     if ((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&
 151         back->in(0) &&
 152         back->in(0)->is_If() &&
 153         back->in(0)->as_If()->_fcnt != COUNT_UNKNOWN &&
 154         back->in(0)->as_If()->_prob != PROB_UNKNOWN) {

 155       break;
 156     }
 157     back = phase->idom(back);
 158   }
 159   if (back != head) {
 160     assert((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&
 161            back->in(0), "if-projection exists");
 162     IfNode* back_if = back->in(0)->as_If();
 163     float loop_back_cnt = back_if->_fcnt * back_if->_prob;
 164 
 165     // Now compute a loop exit count
 166     float loop_exit_cnt = 0.0f;

 167     for( uint i = 0; i < _body.size(); i++ ) {
 168       Node *n = _body[i];
 169       if( n->is_If() ) {
 170         IfNode *iff = n->as_If();
 171         if( iff->_fcnt != COUNT_UNKNOWN && iff->_prob != PROB_UNKNOWN ) {
 172           Node *exit = is_loop_exit(iff);
 173           if( exit ) {
 174             float exit_prob = iff->_prob;
 175             if (exit->Opcode() == Op_IfFalse) exit_prob = 1.0 - exit_prob;
 176             if (exit_prob > PROB_MIN) {
 177               float exit_cnt = iff->_fcnt * exit_prob;
 178               loop_exit_cnt += exit_cnt;



 179             }



 180           }
 181         }
 182       }

 183     }
 184     if (loop_exit_cnt > 0.0f) {
 185       trip_cnt = (loop_back_cnt + loop_exit_cnt) / loop_exit_cnt;
 186     } else {
 187       // No exit count so use
 188       trip_cnt = loop_back_cnt;
 189     }


 190   }
 191 #ifndef PRODUCT
 192   if (TraceProfileTripCount) {
 193     tty->print_cr("compute_profile_trip_cnt  lp: %d cnt: %f\n", head->_idx, trip_cnt);
 194   }
 195 #endif
 196   head->set_profile_trip_cnt(trip_cnt);
 197 }
 198 
 199 //---------------------is_invariant_addition-----------------------------
 200 // Return nonzero index of invariant operand for an Add or Sub
 201 // of (nonconstant) invariant and variant values. Helper for reassociate_invariants.
 202 int IdealLoopTree::is_invariant_addition(Node* n, PhaseIdealLoop *phase) {
 203   int op = n->Opcode();
 204   if (op == Op_AddI || op == Op_SubI) {
 205     bool in1_invar = this->is_invariant(n->in(1));
 206     bool in2_invar = this->is_invariant(n->in(2));
 207     if (in1_invar && !in2_invar) return 1;
 208     if (!in1_invar && in2_invar) return 2;
 209   }


 997   register_new_node(castii, ctrl);
 998   for (DUIterator_Fast imax, i = incr->fast_outs(imax); i < imax; i++) {
 999     Node* n = incr->fast_out(i);
1000     if (n->is_Phi() && n->in(0) == loop) {
1001       int nrep = n->replace_edge(incr, castii);
1002       return castii;
1003     }
1004   }
1005   return NULL;
1006 }
1007 
1008 // Make a copy of the skeleton range check predicates before the main
1009 // loop and set the initial value of loop as input. After unrolling,
1010 // the range of values for the induction variable in the main loop can
1011 // fall outside the allowed range of values by the array access (main
1012 // loop is never executed). When that happens, range check
1013 // CastII/ConvI2L nodes cause some data paths to die. For consistency,
1014 // the control paths must die too but the range checks were removed by
1015 // predication. The range checks that we add here guarantee that they
1016 // do.
1017 void PhaseIdealLoop::duplicate_predicates(CountedLoopNode* pre_head, Node* min_taken, Node* castii,
1018                                           IdealLoopTree* outer_loop, LoopNode* outer_main_head,
1019                                           uint dd_main_head) {
1020   if (UseLoopPredicate) {
1021     Node* entry = pre_head->in(LoopNode::EntryControl);
1022     Node* predicate = NULL;
1023     predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
1024     if (predicate != NULL) {
1025       entry = entry->in(0)->in(0);
1026     }
1027     predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
1028     if (predicate != NULL) {
1029       IfNode* iff = entry->in(0)->as_If();
1030       ProjNode* uncommon_proj = iff->proj_out(1 - entry->as_Proj()->_con);
1031       Node* rgn = uncommon_proj->unique_ctrl_out();
1032       assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
1033       assert(iff->in(1)->in(1)->Opcode() == Op_Opaque1, "unexpected predicate shape");
1034       entry = entry->in(0)->in(0);
1035       Node* prev_proj = min_taken;
1036       while (entry != NULL && entry->is_Proj() && entry->in(0)->is_If()) {
1037         uncommon_proj = entry->in(0)->as_If()->proj_out(1 - entry->as_Proj()->_con);

1038         if (uncommon_proj->unique_ctrl_out() != rgn)
1039           break;
1040         iff = entry->in(0)->as_If();
1041         if (iff->in(1)->Opcode() == Op_Opaque4) {
1042           Node_Stack to_clone(2);
1043           to_clone.push(iff->in(1), 1);
1044           uint current = C->unique();
1045           Node* result = NULL;
1046           // Look for the opaque node to replace with the init value
1047           // and clone everything in between. We keep the Opaque4 node
1048           // so the duplicated predicates are eliminated once loop
1049           // opts are over: they are here only to keep the IR graph
1050           // consistent.
1051           do {
1052             Node* n = to_clone.node();
1053             uint i = to_clone.index();
1054             Node* m = n->in(i);
1055             int op = m->Opcode();
1056             if (m->is_Bool() ||
1057                 m->is_Cmp() ||
1058                 op == Op_AndL ||
1059                 op == Op_OrL ||
1060                 op == Op_RShiftL ||
1061                 op == Op_LShiftL ||
1062                 op == Op_AddL ||
1063                 op == Op_AddI ||
1064                 op == Op_MulL ||
1065                 op == Op_MulI ||
1066                 op == Op_SubL ||
1067                 op == Op_SubI ||
1068                 op == Op_ConvI2L) {
1069               to_clone.push(m, 1);
1070               continue;
1071             }
1072             if (op == Op_Opaque1) {
1073               if (n->_idx < current) {
1074                 n = n->clone();
1075               }
1076               n->set_req(i, castii);
1077               register_new_node(n, min_taken);
1078               to_clone.set_node(n);
1079             }
1080             for (;;) {
1081               Node* cur = to_clone.node();
1082               uint j = to_clone.index();
1083               if (j+1 < cur->req()) {
1084                 to_clone.set_index(j+1);
1085                 break;
1086               }
1087               to_clone.pop();
1088               if (to_clone.size() == 0) {
1089                 result = cur;
1090                 break;
1091               }
1092               Node* next = to_clone.node();
1093               j = to_clone.index();
1094               if (cur->_idx >= current) {
1095                 if (next->_idx < current) {
1096                   next = next->clone();
1097                   register_new_node(next, min_taken);
1098                   to_clone.set_node(next);
1099                 }
1100                 assert(next->in(j) != cur, "input should have been cloned");
1101                 next->set_req(j, cur);
1102               }
1103             }
1104           } while (result == NULL);
1105           assert(result->_idx >= current, "new node expected");
1106 
1107           Node* proj = entry->clone();
1108           Node* other_proj = uncommon_proj->clone();
1109           Node* new_iff = iff->clone();
1110           new_iff->set_req(1, result);
1111           proj->set_req(0, new_iff);
1112           other_proj->set_req(0, new_iff);
1113           Node *frame = new ParmNode(C->start(), TypeFunc::FramePtr);
1114           register_new_node(frame, C->start());
1115           // It's impossible for the predicate to fail at runtime. Use
1116           // an Halt node.
1117           Node* halt = new HaltNode(other_proj, frame);
1118           C->root()->add_req(halt);
1119           new_iff->set_req(0, prev_proj);
1120 
1121           register_control(new_iff, outer_loop->_parent, prev_proj);
1122           register_control(proj, outer_loop->_parent, new_iff);
1123           register_control(other_proj, _ltree_root, new_iff);
1124           register_control(halt, _ltree_root, other_proj);
1125 
1126           prev_proj = proj;
1127         }
1128         entry = entry->in(0)->in(0);
1129       }

1130       _igvn.replace_input_of(outer_main_head, LoopNode::EntryControl, prev_proj);
1131       set_idom(outer_main_head, prev_proj, dd_main_head);
1132     }
1133   }
1134 }
1135 






















1136 //------------------------------insert_pre_post_loops--------------------------
1137 // Insert pre and post loops.  If peel_only is set, the pre-loop can not have
1138 // more iterations added.  It acts as a 'peel' only, no lower-bound RCE, no
1139 // alignment.  Useful to unroll loops that do no array accesses.
1140 void PhaseIdealLoop::insert_pre_post_loops( IdealLoopTree *loop, Node_List &old_new, bool peel_only ) {
1141 
1142 #ifndef PRODUCT
1143   if (TraceLoopOpts) {
1144     if (peel_only)
1145       tty->print("PeelMainPost ");
1146     else
1147       tty->print("PreMainPost  ");
1148     loop->dump_head();
1149   }
1150 #endif
1151   C->set_major_progress();
1152 
1153   // Find common pieces of the loop being guarded with pre & post loops
1154   CountedLoopNode *main_head = loop->_head->as_CountedLoop();
1155   assert( main_head->is_normal_loop(), "" );


1259                                              pre_phi->in(LoopNode::LoopBackControl),
1260                                              visited, clones);
1261       _igvn.hash_delete(main_phi);
1262       main_phi->set_req( LoopNode::EntryControl, fallpre );
1263     }
1264   }
1265 
1266   // Nodes inside the loop may be control dependent on a predicate
1267   // that was moved before the preloop. If the back branch of the main
1268   // or post loops becomes dead, those nodes won't be dependent on the
1269   // test that guards that loop nest anymore which could lead to an
1270   // incorrect array access because it executes independently of the
1271   // test that was guarding the loop nest. We add a special CastII on
1272   // the if branch that enters the loop, between the input induction
1273   // variable value and the induction variable Phi to preserve correct
1274   // dependencies.
1275 
1276   // CastII for the main loop:
1277   Node* castii = cast_incr_before_loop( pre_incr, min_taken, main_head );
1278   assert(castii != NULL, "no castII inserted");
1279   duplicate_predicates(pre_head, min_taken, castii, outer_loop, outer_main_head, dd_main_head);
1280 
1281   // Step B4: Shorten the pre-loop to run only 1 iteration (for now).
1282   // RCE and alignment may change this later.
1283   Node *cmp_end = pre_end->cmp_node();
1284   assert( cmp_end->in(2) == limit, "" );
1285   Node *pre_limit = new AddINode( init, stride );
1286 
1287   // Save the original loop limit in this Opaque1 node for
1288   // use by range check elimination.
1289   Node *pre_opaq  = new Opaque1Node(C, pre_limit, limit);
1290 
1291   register_new_node( pre_limit, pre_head->in(0) );
1292   register_new_node( pre_opaq , pre_head->in(0) );
1293 
1294   // Since no other users of pre-loop compare, I can hack limit directly
1295   assert( cmp_end->outcnt() == 1, "no other users" );
1296   _igvn.hash_delete(cmp_end);
1297   cmp_end->set_req(2, peel_only ? pre_limit : pre_opaq);
1298 
1299   // Special case for not-equal loop bounds:


2796     }
2797   }
2798   assert(iv == cl->phi(), "Wrong phi" );
2799 #endif
2800 
2801   // main and post loops have explicitly created zero trip guard
2802   bool needs_guard = !cl->is_main_loop() && !cl->is_post_loop();
2803   if (needs_guard) {
2804     // Skip guard if values not overlap.
2805     const TypeInt* init_t = phase->_igvn.type(cl->init_trip())->is_int();
2806     const TypeInt* limit_t = phase->_igvn.type(cl->limit())->is_int();
2807     int  stride_con = cl->stride_con();
2808     if (stride_con > 0) {
2809       needs_guard = (init_t->_hi >= limit_t->_lo);
2810     } else {
2811       needs_guard = (init_t->_lo <= limit_t->_hi);
2812     }
2813   }
2814   if (needs_guard) {
2815     // Check for an obvious zero trip guard.
2816     Node* inctrl = PhaseIdealLoop::skip_loop_predicates(cl->skip_predicates());
2817     if (inctrl->Opcode() == Op_IfTrue || inctrl->Opcode() == Op_IfFalse) {
2818       bool maybe_swapped = (inctrl->Opcode() == Op_IfFalse);
2819       // The test should look like just the backedge of a CountedLoop
2820       Node* iff = inctrl->in(0);
2821       if (iff->is_If()) {
2822         Node* bol = iff->in(1);
2823         if (bol->is_Bool()) {
2824           BoolTest test = bol->as_Bool()->_test;
2825           if (maybe_swapped) {
2826             test._test = test.commute();
2827             test._test = test.negate();
2828           }
2829           if (test._test == cl->loopexit()->test_trip()) {
2830             Node* cmp = bol->in(1);
2831             int init_idx = maybe_swapped ? 2 : 1;
2832             int limit_idx = maybe_swapped ? 1 : 2;
2833             if (cmp->is_Cmp() && cmp->in(init_idx) == cl->init_trip() && cmp->in(limit_idx) == cl->limit()) {
2834               needs_guard = false;
2835             }
2836           }




 118     int stride_con = cl->stride_con();
 119     jlong init_con = phase->_igvn.type(init_n)->is_int()->_lo;
 120     jlong limit_con = phase->_igvn.type(limit_n)->is_int()->_hi;
 121     int stride_m   = stride_con - (stride_con > 0 ? 1 : -1);
 122     jlong trip_count = (limit_con - init_con + stride_m)/stride_con;
 123     if (trip_count > 0 && (julong)trip_count < (julong)max_juint) {
 124       if (init_n->is_Con() && limit_n->is_Con()) {
 125         // Set exact trip count.
 126         cl->set_exact_trip_count((uint)trip_count);
 127       } else if (cl->unrolled_count() == 1) {
 128         // Set maximum trip count before unrolling.
 129         cl->set_trip_count((uint)trip_count);
 130       }
 131     }
 132   }
 133 }
 134 
 135 //------------------------------compute_profile_trip_cnt----------------------------
 136 // Compute loop trip count from profile data as
 137 //    (backedge_count + loop_exit_count) / loop_exit_count
 138 
 139 float IdealLoopTree::compute_profile_trip_cnt_helper(Node* n) {
 140   if (n->is_If()) {
 141     IfNode *iff = n->as_If();
 142     if (iff->_fcnt != COUNT_UNKNOWN && iff->_prob != PROB_UNKNOWN) {
 143       Node *exit = is_loop_exit(iff);
 144       if (exit) {
 145         float exit_prob = iff->_prob;
 146         if (exit->Opcode() == Op_IfFalse) exit_prob = 1.0 - exit_prob;
 147         if (exit_prob > PROB_MIN) {
 148           float exit_cnt = iff->_fcnt * exit_prob;
 149           return exit_cnt;
 150         }
 151       }
 152     }
 153   }
 154   if (n->is_Jump()) {
 155     JumpNode *jmp = n->as_Jump();
 156     if (jmp->_fcnt != COUNT_UNKNOWN) {
 157       float* probs = jmp->_probs;
 158       float exit_prob = 0;
 159       PhaseIdealLoop *phase = _phase;
 160       for (DUIterator_Fast imax, i = jmp->fast_outs(imax); i < imax; i++) {
 161         JumpProjNode* u = jmp->fast_out(i)->as_JumpProj();
 162         if (!is_member(_phase->get_loop(u))) {
 163           exit_prob += probs[u->_con];
 164         }
 165       }
 166       return exit_prob * jmp->_fcnt;
 167     }
 168   }
 169   return 0;
 170 }
 171 
 172 void IdealLoopTree::compute_profile_trip_cnt(PhaseIdealLoop *phase) {
 173   if (!_head->is_Loop()) {
 174     return;
 175   }
 176   LoopNode* head = _head->as_Loop();
 177   if (head->profile_trip_cnt() != COUNT_UNKNOWN) {
 178     return; // Already computed
 179   }
 180   float trip_cnt = (float)max_jint; // default is big
 181 
 182   Node* back = head->in(LoopNode::LoopBackControl);
 183   while (back != head) {
 184     if ((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&
 185         back->in(0) &&
 186         back->in(0)->is_If() &&
 187         back->in(0)->as_If()->_fcnt != COUNT_UNKNOWN &&
 188         back->in(0)->as_If()->_prob != PROB_UNKNOWN &&
 189         (back->Opcode() == Op_IfTrue ? 1-back->in(0)->as_If()->_prob : back->in(0)->as_If()->_prob) > PROB_MIN) {
 190       break;
 191     }
 192     back = phase->idom(back);
 193   }
 194   if (back != head) {
 195     assert((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&
 196            back->in(0), "if-projection exists");
 197     IfNode* back_if = back->in(0)->as_If();
 198     float loop_back_cnt = back_if->_fcnt * (back->Opcode() == Op_IfTrue ? back_if->_prob : (1 - back_if->_prob));
 199 
 200     // Now compute a loop exit count
 201     float loop_exit_cnt = 0.0f;
 202     if (_child == NULL) {
 203       for( uint i = 0; i < _body.size(); i++ ) {
 204         Node *n = _body[i];
 205         loop_exit_cnt += compute_profile_trip_cnt_helper(n);
 206       }
 207     } else {
 208       ResourceMark rm;
 209       Unique_Node_List wq;
 210       wq.push(back);
 211       for (uint i = 0; i < wq.size(); i++) {
 212         Node *n = wq.at(i);
 213         assert(n->is_CFG(), "only control nodes");
 214         if (n != head) {
 215           if (n->is_Region()) {
 216             for (uint j = 1; j < n->req(); j++) {
 217               wq.push(n->in(j));
 218             }
 219           } else {
 220             loop_exit_cnt += compute_profile_trip_cnt_helper(n);
 221             wq.push(n->in(0));
 222           }
 223         }
 224       }
 225 
 226     }
 227     if (loop_exit_cnt > 0.0f) {
 228       trip_cnt = (loop_back_cnt + loop_exit_cnt) / loop_exit_cnt;
 229     } else {
 230       // No exit count so use
 231       trip_cnt = loop_back_cnt;
 232     }
 233   } else {
 234     head->mark_profile_trip_failed();
 235   }
 236 #ifndef PRODUCT
 237   if (TraceProfileTripCount) {
 238     tty->print_cr("compute_profile_trip_cnt  lp: %d cnt: %f\n", head->_idx, trip_cnt);
 239   }
 240 #endif
 241   head->set_profile_trip_cnt(trip_cnt);
 242 }
 243 
 244 //---------------------is_invariant_addition-----------------------------
 245 // Return nonzero index of invariant operand for an Add or Sub
 246 // of (nonconstant) invariant and variant values. Helper for reassociate_invariants.
 247 int IdealLoopTree::is_invariant_addition(Node* n, PhaseIdealLoop *phase) {
 248   int op = n->Opcode();
 249   if (op == Op_AddI || op == Op_SubI) {
 250     bool in1_invar = this->is_invariant(n->in(1));
 251     bool in2_invar = this->is_invariant(n->in(2));
 252     if (in1_invar && !in2_invar) return 1;
 253     if (!in1_invar && in2_invar) return 2;
 254   }


1042   register_new_node(castii, ctrl);
1043   for (DUIterator_Fast imax, i = incr->fast_outs(imax); i < imax; i++) {
1044     Node* n = incr->fast_out(i);
1045     if (n->is_Phi() && n->in(0) == loop) {
1046       int nrep = n->replace_edge(incr, castii);
1047       return castii;
1048     }
1049   }
1050   return NULL;
1051 }
1052 
1053 // Make a copy of the skeleton range check predicates before the main
1054 // loop and set the initial value of loop as input. After unrolling,
1055 // the range of values for the induction variable in the main loop can
1056 // fall outside the allowed range of values by the array access (main
1057 // loop is never executed). When that happens, range check
1058 // CastII/ConvI2L nodes cause some data paths to die. For consistency,
1059 // the control paths must die too but the range checks were removed by
1060 // predication. The range checks that we add here guarantee that they
1061 // do.
1062 void PhaseIdealLoop::duplicate_predicates_helper(Node* predicate, Node* castii, IdealLoopTree* outer_loop,
1063                                                  LoopNode* outer_main_head, uint dd_main_head) {





1064   if (predicate != NULL) {
1065     IfNode* iff = predicate->in(0)->as_If();
1066     ProjNode* uncommon_proj = iff->proj_out(1 - predicate->as_Proj()->_con);




1067     Node* rgn = uncommon_proj->unique_ctrl_out();
1068     assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
1069     assert(iff->in(1)->in(1)->Opcode() == Op_Opaque1, "unexpected predicate shape");
1070     predicate = predicate->in(0)->in(0);
1071     Node* current_proj = outer_main_head->in(LoopNode::EntryControl);
1072     Node* prev_proj = current_proj;
1073     while (predicate != NULL && predicate->is_Proj() && predicate->in(0)->is_If()) {
1074       uncommon_proj = predicate->in(0)->as_If()->proj_out(1 - predicate->as_Proj()->_con);
1075       if (uncommon_proj->unique_ctrl_out() != rgn)
1076         break;
1077       iff = predicate->in(0)->as_If();
1078       if (iff->in(1)->Opcode() == Op_Opaque4) {
1079         Node_Stack to_clone(2);
1080         to_clone.push(iff->in(1), 1);
1081         uint current = C->unique();
1082         Node* result = NULL;
1083         // Look for the opaque node to replace with the init value
1084         // and clone everything in between. We keep the Opaque4 node
1085         // so the duplicated predicates are eliminated once loop
1086         // opts are over: they are here only to keep the IR graph
1087         // consistent.
1088         do {
1089           Node* n = to_clone.node();
1090           uint i = to_clone.index();
1091           Node* m = n->in(i);
1092           int op = m->Opcode();
1093           if (m->is_Bool() ||
1094               m->is_Cmp() ||
1095               op == Op_AndL ||
1096               op == Op_OrL ||
1097               op == Op_RShiftL ||
1098               op == Op_LShiftL ||
1099               op == Op_AddL ||
1100               op == Op_AddI ||
1101               op == Op_MulL ||
1102               op == Op_MulI ||
1103               op == Op_SubL ||
1104               op == Op_SubI ||
1105               op == Op_ConvI2L) {
1106             to_clone.push(m, 1);
1107             continue;
1108           }
1109           if (op == Op_Opaque1) {
1110             if (n->_idx < current) {
1111               n = n->clone();
1112             }
1113             n->set_req(i, castii);
1114             register_new_node(n, current_proj);
1115             to_clone.set_node(n);
1116           }
1117           for (;;) {
1118             Node* cur = to_clone.node();
1119             uint j = to_clone.index();
1120             if (j+1 < cur->req()) {
1121               to_clone.set_index(j+1);
1122               break;
1123             }
1124             to_clone.pop();
1125             if (to_clone.size() == 0) {
1126               result = cur;
1127               break;
1128             }
1129             Node* next = to_clone.node();
1130             j = to_clone.index();
1131             if (cur->_idx >= current) {
1132               if (next->_idx < current) {
1133                 next = next->clone();
1134                 register_new_node(next, current_proj);
1135                 to_clone.set_node(next);
1136               }
1137               assert(next->in(j) != cur, "input should have been cloned");
1138               next->set_req(j, cur);
1139             }
1140           }
1141         } while (result == NULL);
1142         assert(result->_idx >= current, "new node expected");
1143 
1144         Node* proj = predicate->clone();
1145         Node* other_proj = uncommon_proj->clone();
1146         Node* new_iff = iff->clone();
1147         new_iff->set_req(1, result);
1148         proj->set_req(0, new_iff);
1149         other_proj->set_req(0, new_iff);
1150         Node *frame = new ParmNode(C->start(), TypeFunc::FramePtr);
1151         register_new_node(frame, C->start());
1152         // It's impossible for the predicate to fail at runtime. Use
1153         // an Halt node.
1154         Node* halt = new HaltNode(other_proj, frame);
1155         C->root()->add_req(halt);
1156         new_iff->set_req(0, prev_proj);
1157 
1158         register_control(new_iff, outer_loop->_parent, prev_proj);
1159         register_control(proj, outer_loop->_parent, new_iff);
1160         register_control(other_proj, _ltree_root, new_iff);
1161         register_control(halt, _ltree_root, other_proj);
1162 
1163         prev_proj = proj;
1164       }
1165       predicate = predicate->in(0)->in(0);
1166     }
1167     if (prev_proj != current_proj) {
1168       _igvn.replace_input_of(outer_main_head, LoopNode::EntryControl, prev_proj);
1169       set_idom(outer_main_head, prev_proj, dd_main_head);
1170     }
1171   }
1172 }
1173 
1174 void PhaseIdealLoop::duplicate_predicates(CountedLoopNode* pre_head, Node* castii, IdealLoopTree* outer_loop,
1175                                           LoopNode* outer_main_head, uint dd_main_head) {
1176   if (UseLoopPredicate) {
1177     Node* entry = pre_head->in(LoopNode::EntryControl);
1178     Node* predicate = NULL;
1179     predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
1180     if (predicate != NULL) {
1181       entry = entry->in(0)->in(0);
1182     }
1183     Node* profile_predicate = NULL;
1184     if (UseProfiledLoopPredicate) {
1185       profile_predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
1186       if (profile_predicate != NULL) {
1187         entry = skip_loop_predicates(entry);
1188       }
1189     }
1190     predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
1191     duplicate_predicates_helper(predicate, castii, outer_loop, outer_main_head, dd_main_head);
1192     duplicate_predicates_helper(profile_predicate, castii, outer_loop, outer_main_head, dd_main_head);
1193   }
1194 }
1195 
1196 //------------------------------insert_pre_post_loops--------------------------
1197 // Insert pre and post loops.  If peel_only is set, the pre-loop can not have
1198 // more iterations added.  It acts as a 'peel' only, no lower-bound RCE, no
1199 // alignment.  Useful to unroll loops that do no array accesses.
1200 void PhaseIdealLoop::insert_pre_post_loops( IdealLoopTree *loop, Node_List &old_new, bool peel_only ) {
1201 
1202 #ifndef PRODUCT
1203   if (TraceLoopOpts) {
1204     if (peel_only)
1205       tty->print("PeelMainPost ");
1206     else
1207       tty->print("PreMainPost  ");
1208     loop->dump_head();
1209   }
1210 #endif
1211   C->set_major_progress();
1212 
1213   // Find common pieces of the loop being guarded with pre & post loops
1214   CountedLoopNode *main_head = loop->_head->as_CountedLoop();
1215   assert( main_head->is_normal_loop(), "" );


1319                                              pre_phi->in(LoopNode::LoopBackControl),
1320                                              visited, clones);
1321       _igvn.hash_delete(main_phi);
1322       main_phi->set_req( LoopNode::EntryControl, fallpre );
1323     }
1324   }
1325 
1326   // Nodes inside the loop may be control dependent on a predicate
1327   // that was moved before the preloop. If the back branch of the main
1328   // or post loops becomes dead, those nodes won't be dependent on the
1329   // test that guards that loop nest anymore which could lead to an
1330   // incorrect array access because it executes independently of the
1331   // test that was guarding the loop nest. We add a special CastII on
1332   // the if branch that enters the loop, between the input induction
1333   // variable value and the induction variable Phi to preserve correct
1334   // dependencies.
1335 
1336   // CastII for the main loop:
1337   Node* castii = cast_incr_before_loop( pre_incr, min_taken, main_head );
1338   assert(castii != NULL, "no castII inserted");
1339   duplicate_predicates(pre_head, castii, outer_loop, outer_main_head, dd_main_head);
1340 
1341   // Step B4: Shorten the pre-loop to run only 1 iteration (for now).
1342   // RCE and alignment may change this later.
1343   Node *cmp_end = pre_end->cmp_node();
1344   assert( cmp_end->in(2) == limit, "" );
1345   Node *pre_limit = new AddINode( init, stride );
1346 
1347   // Save the original loop limit in this Opaque1 node for
1348   // use by range check elimination.
1349   Node *pre_opaq  = new Opaque1Node(C, pre_limit, limit);
1350 
1351   register_new_node( pre_limit, pre_head->in(0) );
1352   register_new_node( pre_opaq , pre_head->in(0) );
1353 
1354   // Since no other users of pre-loop compare, I can hack limit directly
1355   assert( cmp_end->outcnt() == 1, "no other users" );
1356   _igvn.hash_delete(cmp_end);
1357   cmp_end->set_req(2, peel_only ? pre_limit : pre_opaq);
1358 
1359   // Special case for not-equal loop bounds:


2856     }
2857   }
2858   assert(iv == cl->phi(), "Wrong phi" );
2859 #endif
2860 
2861   // main and post loops have explicitly created zero trip guard
2862   bool needs_guard = !cl->is_main_loop() && !cl->is_post_loop();
2863   if (needs_guard) {
2864     // Skip guard if values not overlap.
2865     const TypeInt* init_t = phase->_igvn.type(cl->init_trip())->is_int();
2866     const TypeInt* limit_t = phase->_igvn.type(cl->limit())->is_int();
2867     int  stride_con = cl->stride_con();
2868     if (stride_con > 0) {
2869       needs_guard = (init_t->_hi >= limit_t->_lo);
2870     } else {
2871       needs_guard = (init_t->_lo <= limit_t->_hi);
2872     }
2873   }
2874   if (needs_guard) {
2875     // Check for an obvious zero trip guard.
2876     Node* inctrl = PhaseIdealLoop::skip_all_loop_predicates(cl->skip_predicates());
2877     if (inctrl->Opcode() == Op_IfTrue || inctrl->Opcode() == Op_IfFalse) {
2878       bool maybe_swapped = (inctrl->Opcode() == Op_IfFalse);
2879       // The test should look like just the backedge of a CountedLoop
2880       Node* iff = inctrl->in(0);
2881       if (iff->is_If()) {
2882         Node* bol = iff->in(1);
2883         if (bol->is_Bool()) {
2884           BoolTest test = bol->as_Bool()->_test;
2885           if (maybe_swapped) {
2886             test._test = test.commute();
2887             test._test = test.negate();
2888           }
2889           if (test._test == cl->loopexit()->test_trip()) {
2890             Node* cmp = bol->in(1);
2891             int init_idx = maybe_swapped ? 2 : 1;
2892             int limit_idx = maybe_swapped ? 1 : 2;
2893             if (cmp->is_Cmp() && cmp->in(init_idx) == cl->init_trip() && cmp->in(limit_idx) == cl->limit()) {
2894               needs_guard = false;
2895             }
2896           }


< prev index next >