Mercurial > hg > graal-jvmci-8
comparison src/share/vm/opto/loopTransform.cpp @ 2453:d7a3fed1c1c9
7004547: regular loop unroll should not unroll more than max unrolling
Summary: Take into account that after unroll conjoined heads and tails will fold.
Reviewed-by: never
author | kvn |
---|---|
date | Mon, 04 Apr 2011 19:02:36 -0700 |
parents | 8b2317d732ec |
children | 3af54845df98 |
comparison
equal
deleted
inserted
replaced
2450:a54519951ff6 | 2453:d7a3fed1c1c9 |
---|---|
520 peeled_dom_test_elim(loop,old_new); | 520 peeled_dom_test_elim(loop,old_new); |
521 | 521 |
522 loop->record_for_igvn(); | 522 loop->record_for_igvn(); |
523 } | 523 } |
524 | 524 |
525 #define EMPTY_LOOP_SIZE 7 // number of nodes in an empty loop | |
526 | |
525 //------------------------------policy_maximally_unroll------------------------ | 527 //------------------------------policy_maximally_unroll------------------------ |
526 // Return exact loop trip count, or 0 if not maximally unrolling | 528 // Calculate exact loop trip count and return true if loop can be maximally |
529 // unrolled. | |
527 bool IdealLoopTree::policy_maximally_unroll( PhaseIdealLoop *phase ) const { | 530 bool IdealLoopTree::policy_maximally_unroll( PhaseIdealLoop *phase ) const { |
528 CountedLoopNode *cl = _head->as_CountedLoop(); | 531 CountedLoopNode *cl = _head->as_CountedLoop(); |
529 assert(cl->is_normal_loop(), ""); | 532 assert(cl->is_normal_loop(), ""); |
533 if (!cl->is_valid_counted_loop()) | |
534 return false; // Malformed counted loop | |
530 | 535 |
531 Node *init_n = cl->init_trip(); | 536 Node *init_n = cl->init_trip(); |
532 Node *limit_n = cl->limit(); | 537 Node *limit_n = cl->limit(); |
533 | 538 |
534 // Non-constant bounds | 539 // Non-constant bounds |
535 if (init_n == NULL || !init_n->is_Con() || | 540 if (init_n == NULL || !init_n->is_Con() || |
536 limit_n == NULL || !limit_n->is_Con() || | 541 limit_n == NULL || !limit_n->is_Con()) { |
537 // protect against stride not being a constant | |
538 !cl->stride_is_con()) { | |
539 return false; | 542 return false; |
540 } | 543 } |
541 int init = init_n->get_int(); | 544 // Use longs to avoid integer overflow. |
542 int limit = limit_n->get_int(); | 545 int stride_con = cl->stride_con(); |
543 int span = limit - init; | 546 long init_con = cl->init_trip()->get_int(); |
544 int stride = cl->stride_con(); | 547 long limit_con = cl->limit()->get_int(); |
545 | 548 int stride_m = stride_con - (stride_con > 0 ? 1 : -1); |
546 if (init >= limit || stride > span) { | 549 long trip_cnt = (limit_con - init_con + stride_m)/stride_con; |
550 | |
551 // Note, max_jint is used to indicate unknown trip count. | |
552 if (trip_cnt <= 0 || trip_cnt >= (long)max_jint) { | |
547 // return a false (no maximally unroll) and the regular unroll/peel | 553 // return a false (no maximally unroll) and the regular unroll/peel |
548 // route will make a small mess which CCP will fold away. | 554 // route will make a small mess which CCP will fold away. |
549 return false; | 555 return false; |
550 } | 556 } |
551 uint trip_count = span/stride; // trip_count can be greater than 2 Gig. | 557 uint trip_count = (uint)trip_cnt; |
552 assert( (int)trip_count*stride == span, "must divide evenly" ); | 558 cl->set_trip_count(trip_count); |
553 | 559 |
554 // Real policy: if we maximally unroll, does it get too big? | 560 // Real policy: if we maximally unroll, does it get too big? |
555 // Allow the unrolled mess to get larger than standard loop | 561 // Allow the unrolled mess to get larger than standard loop |
556 // size. After all, it will no longer be a loop. | 562 // size. After all, it will no longer be a loop. |
557 uint body_size = _body.size(); | 563 uint body_size = _body.size(); |
558 uint unroll_limit = (uint)LoopUnrollLimit * 4; | 564 uint unroll_limit = (uint)LoopUnrollLimit * 4; |
559 assert( (intx)unroll_limit == LoopUnrollLimit * 4, "LoopUnrollLimit must fit in 32bits"); | 565 assert( (intx)unroll_limit == LoopUnrollLimit * 4, "LoopUnrollLimit must fit in 32bits"); |
560 cl->set_trip_count(trip_count); | |
561 if (trip_count > unroll_limit || body_size > unroll_limit) { | 566 if (trip_count > unroll_limit || body_size > unroll_limit) { |
567 return false; | |
568 } | |
569 | |
570 // Take into account that after unroll conjoined heads and tails will fold, | |
571 // otherwise policy_unroll() may allow more unrolling than max unrolling. | |
572 uint new_body_size = EMPTY_LOOP_SIZE + (body_size - EMPTY_LOOP_SIZE) * trip_count; | |
573 uint tst_body_size = (new_body_size - EMPTY_LOOP_SIZE) / trip_count + EMPTY_LOOP_SIZE; | |
574 if (body_size != tst_body_size) // Check for int overflow | |
575 return false; | |
576 if (new_body_size > unroll_limit || | |
577 // Unrolling can result in a large amount of node construction | |
578 new_body_size >= MaxNodeLimit - phase->C->unique()) { | |
562 return false; | 579 return false; |
563 } | 580 } |
564 | 581 |
565 // Currently we don't have policy to optimize one iteration loops. | 582 // Currently we don't have policy to optimize one iteration loops. |
566 // Maximally unrolling transformation is used for that: | 583 // Maximally unrolling transformation is used for that: |
567 // it is peeled and the original loop become non reachable (dead). | 584 // it is peeled and the original loop become non reachable (dead). |
568 if (trip_count == 1) | 585 // Also fully unroll a loop with few iterations regardless next |
586 // conditions since following loop optimizations will split | |
587 // such loop anyway (pre-main-post). | |
588 if (trip_count <= 3) | |
569 return true; | 589 return true; |
570 | 590 |
571 // Do not unroll a loop with String intrinsics code. | 591 // Do not unroll a loop with String intrinsics code. |
572 // String intrinsics are large and have loops. | 592 // String intrinsics are large and have loops. |
573 for (uint k = 0; k < _body.size(); k++) { | 593 for (uint k = 0; k < _body.size(); k++) { |
580 return false; | 600 return false; |
581 } | 601 } |
582 } // switch | 602 } // switch |
583 } | 603 } |
584 | 604 |
585 if (body_size <= unroll_limit) { | 605 return true; // Do maximally unroll |
586 uint new_body_size = body_size * trip_count; | |
587 if (new_body_size <= unroll_limit && | |
588 body_size == new_body_size / trip_count && | |
589 // Unrolling can result in a large amount of node construction | |
590 new_body_size < MaxNodeLimit - phase->C->unique()) { | |
591 return true; // maximally unroll | |
592 } | |
593 } | |
594 | |
595 return false; // Do not maximally unroll | |
596 } | 606 } |
597 | 607 |
598 | 608 |
599 //------------------------------policy_unroll---------------------------------- | 609 //------------------------------policy_unroll---------------------------------- |
600 // Return TRUE or FALSE if the loop should be unrolled or not. Unroll if | 610 // Return TRUE or FALSE if the loop should be unrolled or not. Unroll if |
602 bool IdealLoopTree::policy_unroll( PhaseIdealLoop *phase ) const { | 612 bool IdealLoopTree::policy_unroll( PhaseIdealLoop *phase ) const { |
603 | 613 |
604 CountedLoopNode *cl = _head->as_CountedLoop(); | 614 CountedLoopNode *cl = _head->as_CountedLoop(); |
605 assert(cl->is_normal_loop() || cl->is_main_loop(), ""); | 615 assert(cl->is_normal_loop() || cl->is_main_loop(), ""); |
606 | 616 |
607 // protect against stride not being a constant | 617 if (!cl->is_valid_counted_loop()) |
608 if (!cl->stride_is_con()) return false; | 618 return false; // Malformed counted loop |
609 | 619 |
610 // protect against over-unrolling | 620 // protect against over-unrolling |
611 if (cl->trip_count() <= 1) return false; | 621 if (cl->trip_count() <= 1) return false; |
622 | |
623 // Check for stride being a small enough constant | |
624 if (abs(cl->stride_con()) > (1<<3)) return false; | |
612 | 625 |
613 int future_unroll_ct = cl->unrolled_count() * 2; | 626 int future_unroll_ct = cl->unrolled_count() * 2; |
614 | 627 |
615 // Don't unroll if the next round of unrolling would push us | 628 // Don't unroll if the next round of unrolling would push us |
616 // over the expected trip count of the loop. One is subtracted | 629 // over the expected trip count of the loop. One is subtracted |
688 if (xors_in_loop >= 4 && body_size < (uint)LoopUnrollLimit*4) return true; | 701 if (xors_in_loop >= 4 && body_size < (uint)LoopUnrollLimit*4) return true; |
689 // Normal case: loop too big | 702 // Normal case: loop too big |
690 return false; | 703 return false; |
691 } | 704 } |
692 | 705 |
693 // Check for stride being a small enough constant | |
694 if (abs(cl->stride_con()) > (1<<3)) return false; | |
695 | |
696 // Unroll once! (Each trip will soon do double iterations) | 706 // Unroll once! (Each trip will soon do double iterations) |
697 return true; | 707 return true; |
698 } | 708 } |
699 | 709 |
700 //------------------------------policy_align----------------------------------- | 710 //------------------------------policy_align----------------------------------- |
1084 #ifndef PRODUCT | 1094 #ifndef PRODUCT |
1085 if (PrintOpto && VerifyLoopOptimizations) { | 1095 if (PrintOpto && VerifyLoopOptimizations) { |
1086 tty->print("Unrolling "); | 1096 tty->print("Unrolling "); |
1087 loop->dump_head(); | 1097 loop->dump_head(); |
1088 } else if (TraceLoopOpts) { | 1098 } else if (TraceLoopOpts) { |
1089 tty->print("Unroll %d ", loop_head->unrolled_count()*2); | 1099 if (loop_head->trip_count() < LoopUnrollLimit) { |
1100 tty->print("Unroll %d(%2d) ", loop_head->unrolled_count()*2, loop_head->trip_count()); | |
1101 } else { | |
1102 tty->print("Unroll %d ", loop_head->unrolled_count()*2); | |
1103 } | |
1090 loop->dump_head(); | 1104 loop->dump_head(); |
1091 } | 1105 } |
1092 #endif | 1106 #endif |
1093 | 1107 |
1094 // Remember loop node count before unrolling to detect | 1108 // Remember loop node count before unrolling to detect |
1759 // Micro-benchmark spamming. Policy is to always remove empty loops. | 1773 // Micro-benchmark spamming. Policy is to always remove empty loops. |
1760 // The 'DO' part is to replace the trip counter with the value it will | 1774 // The 'DO' part is to replace the trip counter with the value it will |
1761 // have on the last iteration. This will break the loop. | 1775 // have on the last iteration. This will break the loop. |
1762 bool IdealLoopTree::policy_do_remove_empty_loop( PhaseIdealLoop *phase ) { | 1776 bool IdealLoopTree::policy_do_remove_empty_loop( PhaseIdealLoop *phase ) { |
1763 // Minimum size must be empty loop | 1777 // Minimum size must be empty loop |
1764 if (_body.size() > 7/*number of nodes in an empty loop*/) | 1778 if (_body.size() > EMPTY_LOOP_SIZE) |
1765 return false; | 1779 return false; |
1766 | 1780 |
1767 if (!_head->is_CountedLoop()) | 1781 if (!_head->is_CountedLoop()) |
1768 return false; // Dead loop | 1782 return false; // Dead loop |
1769 CountedLoopNode *cl = _head->as_CountedLoop(); | 1783 CountedLoopNode *cl = _head->as_CountedLoop(); |
1885 phase->do_maximally_unroll(this,old_new); | 1899 phase->do_maximally_unroll(this,old_new); |
1886 return true; | 1900 return true; |
1887 } | 1901 } |
1888 } | 1902 } |
1889 | 1903 |
1904 // Skip next optimizations if running low on nodes. Note that | |
1905 // policy_unswitching and policy_maximally_unroll have this check. | |
1906 uint nodes_left = MaxNodeLimit - phase->C->unique(); | |
1907 if ((2 * _body.size()) > nodes_left) { | |
1908 return true; | |
1909 } | |
1890 | 1910 |
1891 // Counted loops may be peeled, may need some iterations run up | 1911 // Counted loops may be peeled, may need some iterations run up |
1892 // front for RCE, and may want to align loop refs to a cache | 1912 // front for RCE, and may want to align loop refs to a cache |
1893 // line. Thus we clone a full loop up front whose trip count is | 1913 // line. Thus we clone a full loop up front whose trip count is |
1894 // at least 1 (if peeling), but may be several more. | 1914 // at least 1 (if peeling), but may be several more. |