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