252
253 //---------------------reassociate_invariants-----------------------------
254 // Reassociate invariant expressions:
255 void IdealLoopTree::reassociate_invariants(PhaseIdealLoop *phase) {
256 for (int i = _body.size() - 1; i >= 0; i--) {
257 Node *n = _body.at(i);
258 for (int j = 0; j < 5; j++) {
259 Node* nn = reassociate_add_sub(n, phase);
260 if (nn == NULL) break;
261 n = nn; // again
262 };
263 }
264 }
265
266 //------------------------------policy_peeling---------------------------------
267 // Return TRUE or FALSE if the loop should be peeled or not. Peel if we can
268 // make some loop-invariant test (usually a null-check) happen before the loop.
269 bool IdealLoopTree::policy_peeling( PhaseIdealLoop *phase ) const {
270 Node *test = ((IdealLoopTree*)this)->tail();
271 int body_size = ((IdealLoopTree*)this)->_body.size();
272 int uniq = phase->C->unique();
273 // Peeling does loop cloning which can result in O(N^2) node construction
274 if( body_size > 255 /* Prevent overflow for large body_size */
275 || (body_size * body_size + uniq > MaxNodeLimit) ) {
276 return false; // too large to safely clone
277 }
278 while( test != _head ) { // Scan till run off top of loop
279 if( test->is_If() ) { // Test?
280 Node *ctrl = phase->get_ctrl(test->in(1));
281 if (ctrl->is_top())
282 return false; // Found dead test on live IF? No peeling!
283 // Standard IF only has one input value to check for loop invariance
284 assert( test->Opcode() == Op_If || test->Opcode() == Op_CountedLoopEnd, "Check this code when new subtype is added");
285 // Condition is not a member of this loop?
286 if( !is_member(phase->get_loop(ctrl)) &&
287 is_loop_exit(test) )
288 return true; // Found reason to peel!
289 }
290 // Walk up dominators to loop _head looking for test which is
291 // executed on every path thru loop.
292 test = phase->idom(test);
293 }
294 return false;
295 }
584 uint unroll_limit = (uint)LoopUnrollLimit * 4;
585 assert( (intx)unroll_limit == LoopUnrollLimit * 4, "LoopUnrollLimit must fit in 32bits");
586 if (trip_count > unroll_limit || body_size > unroll_limit) {
587 return false;
588 }
589
590 // Fully unroll a loop with few iterations regardless next
591 // conditions since following loop optimizations will split
592 // such loop anyway (pre-main-post).
593 if (trip_count <= 3)
594 return true;
595
596 // Take into account that after unroll conjoined heads and tails will fold,
597 // otherwise policy_unroll() may allow more unrolling than max unrolling.
598 uint new_body_size = EMPTY_LOOP_SIZE + (body_size - EMPTY_LOOP_SIZE) * trip_count;
599 uint tst_body_size = (new_body_size - EMPTY_LOOP_SIZE) / trip_count + EMPTY_LOOP_SIZE;
600 if (body_size != tst_body_size) // Check for int overflow
601 return false;
602 if (new_body_size > unroll_limit ||
603 // Unrolling can result in a large amount of node construction
604 new_body_size >= MaxNodeLimit - phase->C->unique()) {
605 return false;
606 }
607
608 // Do not unroll a loop with String intrinsics code.
609 // String intrinsics are large and have loops.
610 for (uint k = 0; k < _body.size(); k++) {
611 Node* n = _body.at(k);
612 switch (n->Opcode()) {
613 case Op_StrComp:
614 case Op_StrEquals:
615 case Op_StrIndexOf:
616 case Op_AryEq: {
617 return false;
618 }
619 } // switch
620 }
621
622 return true; // Do maximally unroll
623 }
624
2251 compute_profile_trip_cnt(phase);
2252
2253 // Before attempting fancy unrolling, RCE or alignment, see if we want
2254 // to completely unroll this loop or do loop unswitching.
2255 if (cl->is_normal_loop()) {
2256 if (should_unswitch) {
2257 phase->do_unswitching(this, old_new);
2258 return true;
2259 }
2260 bool should_maximally_unroll = policy_maximally_unroll(phase);
2261 if (should_maximally_unroll) {
2262 // Here we did some unrolling and peeling. Eventually we will
2263 // completely unroll this loop and it will no longer be a loop.
2264 phase->do_maximally_unroll(this,old_new);
2265 return true;
2266 }
2267 }
2268
2269 // Skip next optimizations if running low on nodes. Note that
2270 // policy_unswitching and policy_maximally_unroll have this check.
2271 uint nodes_left = MaxNodeLimit - phase->C->unique();
2272 if ((2 * _body.size()) > nodes_left) {
2273 return true;
2274 }
2275
2276 // Counted loops may be peeled, may need some iterations run up
2277 // front for RCE, and may want to align loop refs to a cache
2278 // line. Thus we clone a full loop up front whose trip count is
2279 // at least 1 (if peeling), but may be several more.
2280
2281 // The main loop will start cache-line aligned with at least 1
2282 // iteration of the unrolled body (zero-trip test required) and
2283 // will have some range checks removed.
2284
2285 // A post-loop will finish any odd iterations (leftover after
2286 // unrolling), plus any needed for RCE purposes.
2287
2288 bool should_unroll = policy_unroll(phase);
2289
2290 bool should_rce = policy_range_check(phase);
2291
|
252
253 //---------------------reassociate_invariants-----------------------------
254 // Reassociate invariant expressions:
255 void IdealLoopTree::reassociate_invariants(PhaseIdealLoop *phase) {
256 for (int i = _body.size() - 1; i >= 0; i--) {
257 Node *n = _body.at(i);
258 for (int j = 0; j < 5; j++) {
259 Node* nn = reassociate_add_sub(n, phase);
260 if (nn == NULL) break;
261 n = nn; // again
262 };
263 }
264 }
265
266 //------------------------------policy_peeling---------------------------------
267 // Return TRUE or FALSE if the loop should be peeled or not. Peel if we can
268 // make some loop-invariant test (usually a null-check) happen before the loop.
269 bool IdealLoopTree::policy_peeling( PhaseIdealLoop *phase ) const {
270 Node *test = ((IdealLoopTree*)this)->tail();
271 int body_size = ((IdealLoopTree*)this)->_body.size();
272 int live_node_count = phase->C->live_nodes();
273 // Peeling does loop cloning which can result in O(N^2) node construction
274 if( body_size > 255 /* Prevent overflow for large body_size */
275 || (body_size * body_size + live_node_count > MaxNodeLimit) ) {
276 return false; // too large to safely clone
277 }
278 while( test != _head ) { // Scan till run off top of loop
279 if( test->is_If() ) { // Test?
280 Node *ctrl = phase->get_ctrl(test->in(1));
281 if (ctrl->is_top())
282 return false; // Found dead test on live IF? No peeling!
283 // Standard IF only has one input value to check for loop invariance
284 assert( test->Opcode() == Op_If || test->Opcode() == Op_CountedLoopEnd, "Check this code when new subtype is added");
285 // Condition is not a member of this loop?
286 if( !is_member(phase->get_loop(ctrl)) &&
287 is_loop_exit(test) )
288 return true; // Found reason to peel!
289 }
290 // Walk up dominators to loop _head looking for test which is
291 // executed on every path thru loop.
292 test = phase->idom(test);
293 }
294 return false;
295 }
584 uint unroll_limit = (uint)LoopUnrollLimit * 4;
585 assert( (intx)unroll_limit == LoopUnrollLimit * 4, "LoopUnrollLimit must fit in 32bits");
586 if (trip_count > unroll_limit || body_size > unroll_limit) {
587 return false;
588 }
589
590 // Fully unroll a loop with few iterations regardless next
591 // conditions since following loop optimizations will split
592 // such loop anyway (pre-main-post).
593 if (trip_count <= 3)
594 return true;
595
596 // Take into account that after unroll conjoined heads and tails will fold,
597 // otherwise policy_unroll() may allow more unrolling than max unrolling.
598 uint new_body_size = EMPTY_LOOP_SIZE + (body_size - EMPTY_LOOP_SIZE) * trip_count;
599 uint tst_body_size = (new_body_size - EMPTY_LOOP_SIZE) / trip_count + EMPTY_LOOP_SIZE;
600 if (body_size != tst_body_size) // Check for int overflow
601 return false;
602 if (new_body_size > unroll_limit ||
603 // Unrolling can result in a large amount of node construction
604 new_body_size >= MaxNodeLimit - (uint) phase->C->live_nodes()) {
605 return false;
606 }
607
608 // Do not unroll a loop with String intrinsics code.
609 // String intrinsics are large and have loops.
610 for (uint k = 0; k < _body.size(); k++) {
611 Node* n = _body.at(k);
612 switch (n->Opcode()) {
613 case Op_StrComp:
614 case Op_StrEquals:
615 case Op_StrIndexOf:
616 case Op_AryEq: {
617 return false;
618 }
619 } // switch
620 }
621
622 return true; // Do maximally unroll
623 }
624
2251 compute_profile_trip_cnt(phase);
2252
2253 // Before attempting fancy unrolling, RCE or alignment, see if we want
2254 // to completely unroll this loop or do loop unswitching.
2255 if (cl->is_normal_loop()) {
2256 if (should_unswitch) {
2257 phase->do_unswitching(this, old_new);
2258 return true;
2259 }
2260 bool should_maximally_unroll = policy_maximally_unroll(phase);
2261 if (should_maximally_unroll) {
2262 // Here we did some unrolling and peeling. Eventually we will
2263 // completely unroll this loop and it will no longer be a loop.
2264 phase->do_maximally_unroll(this,old_new);
2265 return true;
2266 }
2267 }
2268
2269 // Skip next optimizations if running low on nodes. Note that
2270 // policy_unswitching and policy_maximally_unroll have this check.
2271 uint nodes_left = MaxNodeLimit - (uint) phase->C->live_nodes();
2272 if ((2 * _body.size()) > nodes_left) {
2273 return true;
2274 }
2275
2276 // Counted loops may be peeled, may need some iterations run up
2277 // front for RCE, and may want to align loop refs to a cache
2278 // line. Thus we clone a full loop up front whose trip count is
2279 // at least 1 (if peeling), but may be several more.
2280
2281 // The main loop will start cache-line aligned with at least 1
2282 // iteration of the unrolled body (zero-trip test required) and
2283 // will have some range checks removed.
2284
2285 // A post-loop will finish any odd iterations (leftover after
2286 // unrolling), plus any needed for RCE purposes.
2287
2288 bool should_unroll = policy_unroll(phase);
2289
2290 bool should_rce = policy_range_check(phase);
2291
|