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 }
|