Mercurial > hg > truffle

comparison src/share/vm/opto/loopTransform.cpp @ 2465:3af54845df98

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
7004555: Add new policy for one iteration loops Summary: Add new policy for one iteration loops (mostly formal pre- loops). Reviewed-by: never
author kvn
date Fri, 08 Apr 2011 14:56:22 -0700
parents d7a3fed1c1c9
children 6c97c830fb6f
comparison
equal deleted inserted replaced
2463:3f49d30f8184 2465:3af54845df98
58 // Put loop body on igvn work list 58 // Put loop body on igvn work list
59 void IdealLoopTree::record_for_igvn() { 59 void IdealLoopTree::record_for_igvn() {
60 for( uint i = 0; i < _body.size(); i++ ) { 60 for( uint i = 0; i < _body.size(); i++ ) {
61 Node *n = _body.at(i); 61 Node *n = _body.at(i);
62 _phase->_igvn._worklist.push(n); 62 _phase->_igvn._worklist.push(n);
63 }
64 }
65
66 //------------------------------compute_exact_trip_count-----------------------
67 // Compute loop exact trip count if possible. Do not recalculate trip count for
68 // split loops (pre-main-post) which have their limits and inits behind Opaque node.
69 void IdealLoopTree::compute_exact_trip_count( PhaseIdealLoop *phase ) {
70 if (!_head->as_Loop()->is_valid_counted_loop()) {
71 return;
72 }
73 CountedLoopNode* cl = _head->as_CountedLoop();
74 // Trip count may become nonexact for iteration split loops since
75 // RCE modifies limits. Note, _trip_count value is not reset since
76 // it is used to limit unrolling of main loop.
77 cl->set_nonexact_trip_count();
78
79 // Loop's test should be part of loop.
80 if (!phase->is_member(this, phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue))))
81 return; // Infinite loop
82
83 #ifdef ASSERT
84 BoolTest::mask bt = cl->loopexit()->test_trip();
85 assert(bt == BoolTest::lt || bt == BoolTest::gt ||
86 bt == BoolTest::ne, "canonical test is expected");
87 #endif
88
89 Node* init_n = cl->init_trip();
90 Node* limit_n = cl->limit();
91 if (init_n != NULL && init_n->is_Con() &&
92 limit_n != NULL && limit_n->is_Con()) {
93 // Use longs to avoid integer overflow.
94 int stride_con = cl->stride_con();
95 long init_con = cl->init_trip()->get_int();
96 long limit_con = cl->limit()->get_int();
97 int stride_m = stride_con - (stride_con > 0 ? 1 : -1);
98 long trip_count = (limit_con - init_con + stride_m)/stride_con;
99 if (trip_count > 0 && (julong)trip_count < (julong)max_juint) {
100 // Set exact trip count.
101 cl->set_exact_trip_count((uint)trip_count);
102 }
63 } 103 }
64 } 104 }
65 105
66 //------------------------------compute_profile_trip_cnt---------------------------- 106 //------------------------------compute_profile_trip_cnt----------------------------
67 // Compute loop trip count from profile data as 107 // Compute loop trip count from profile data as
531 CountedLoopNode *cl = _head->as_CountedLoop(); 571 CountedLoopNode *cl = _head->as_CountedLoop();
532 assert(cl->is_normal_loop(), ""); 572 assert(cl->is_normal_loop(), "");
533 if (!cl->is_valid_counted_loop()) 573 if (!cl->is_valid_counted_loop())
534 return false; // Malformed counted loop 574 return false; // Malformed counted loop
535 575
536 Node *init_n = cl->init_trip(); 576 if (!cl->has_exact_trip_count()) {
537 Node *limit_n = cl->limit(); 577 // Trip count is not exact.
538
539 // Non-constant bounds
540 if (init_n == NULL || !init_n->is_Con() ||
541 limit_n == NULL || !limit_n->is_Con()) {
542 return false; 578 return false;
543 } 579 }
544 // Use longs to avoid integer overflow. 580
545 int stride_con = cl->stride_con(); 581 uint trip_count = cl->trip_count();
546 long init_con = cl->init_trip()->get_int(); 582 // Note, max_juint is used to indicate unknown trip count.
547 long limit_con = cl->limit()->get_int(); 583 assert(trip_count > 1, "one iteration loop should be optimized out already");
548 int stride_m = stride_con - (stride_con > 0 ? 1 : -1); 584 assert(trip_count < max_juint, "exact trip_count should be less than max_uint.");
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) {
553 // return a false (no maximally unroll) and the regular unroll/peel
554 // route will make a small mess which CCP will fold away.
555 return false;
556 }
557 uint trip_count = (uint)trip_cnt;
558 cl->set_trip_count(trip_count);
559 585
560 // Real policy: if we maximally unroll, does it get too big? 586 // Real policy: if we maximally unroll, does it get too big?
561 // Allow the unrolled mess to get larger than standard loop 587 // Allow the unrolled mess to get larger than standard loop
562 // size. After all, it will no longer be a loop. 588 // size. After all, it will no longer be a loop.
563 uint body_size = _body.size(); 589 uint body_size = _body.size();
1094 #ifndef PRODUCT 1120 #ifndef PRODUCT
1095 if (PrintOpto && VerifyLoopOptimizations) { 1121 if (PrintOpto && VerifyLoopOptimizations) {
1096 tty->print("Unrolling "); 1122 tty->print("Unrolling ");
1097 loop->dump_head(); 1123 loop->dump_head();
1098 } else if (TraceLoopOpts) { 1124 } else if (TraceLoopOpts) {
1099 if (loop_head->trip_count() < LoopUnrollLimit) { 1125 if (loop_head->trip_count() < (uint)LoopUnrollLimit) {
1100 tty->print("Unroll %d(%2d) ", loop_head->unrolled_count()*2, loop_head->trip_count()); 1126 tty->print("Unroll %d(%2d) ", loop_head->unrolled_count()*2, loop_head->trip_count());
1101 } else { 1127 } else {
1102 tty->print("Unroll %d ", loop_head->unrolled_count()*2); 1128 tty->print("Unroll %d ", loop_head->unrolled_count()*2);
1103 } 1129 }
1104 loop->dump_head(); 1130 loop->dump_head();
1800 #endif 1826 #endif
1801 1827
1802 // main and post loops have explicitly created zero trip guard 1828 // main and post loops have explicitly created zero trip guard
1803 bool needs_guard = !cl->is_main_loop() && !cl->is_post_loop(); 1829 bool needs_guard = !cl->is_main_loop() && !cl->is_post_loop();
1804 if (needs_guard) { 1830 if (needs_guard) {
1831 // Skip guard if values not overlap.
1832 const TypeInt* init_t = phase->_igvn.type(cl->init_trip())->is_int();
1833 const TypeInt* limit_t = phase->_igvn.type(cl->limit())->is_int();
1834 int stride_con = cl->stride_con();
1835 if (stride_con > 0) {
1836 needs_guard = (init_t->_hi >= limit_t->_lo);
1837 } else {
1838 needs_guard = (init_t->_lo <= limit_t->_hi);
1839 }
1840 }
1841 if (needs_guard) {
1805 // Check for an obvious zero trip guard. 1842 // Check for an obvious zero trip guard.
1806 Node* inctrl = PhaseIdealLoop::skip_loop_predicates(cl->in(LoopNode::EntryControl)); 1843 Node* inctrl = PhaseIdealLoop::skip_loop_predicates(cl->in(LoopNode::EntryControl));
1807 if (inctrl->Opcode() == Op_IfTrue) { 1844 if (inctrl->Opcode() == Op_IfTrue) {
1808 // The test should look like just the backedge of a CountedLoop 1845 // The test should look like just the backedge of a CountedLoop
1809 Node* iff = inctrl->in(0); 1846 Node* iff = inctrl->in(0);
1844 phase->_igvn.replace_node(phi,final); 1881 phase->_igvn.replace_node(phi,final);
1845 phase->C->set_major_progress(); 1882 phase->C->set_major_progress();
1846 return true; 1883 return true;
1847 } 1884 }
1848 1885
1886 //------------------------------policy_do_one_iteration_loop-------------------
1887 // Convert one iteration loop into normal code.
1888 bool IdealLoopTree::policy_do_one_iteration_loop( PhaseIdealLoop *phase ) {
1889 if (!_head->as_Loop()->is_valid_counted_loop())
1890 return false; // Only for counted loop
1891
1892 CountedLoopNode *cl = _head->as_CountedLoop();
1893 if (!cl->has_exact_trip_count() || cl->trip_count() != 1) {
1894 return false;
1895 }
1896
1897 #ifndef PRODUCT
1898 if(TraceLoopOpts) {
1899 tty->print("OneIteration ");
1900 this->dump_head();
1901 }
1902 #endif
1903
1904 Node *init_n = cl->init_trip();
1905 #ifdef ASSERT
1906 // Loop boundaries should be constant since trip count is exact.
1907 assert(init_n->get_int() + cl->stride_con() >= cl->limit()->get_int(), "should be one iteration");
1908 #endif
1909 // Replace the phi at loop head with the value of the init_trip.
1910 // Then the CountedLoopEnd will collapse (backedge will not be taken)
1911 // and all loop-invariant uses of the exit values will be correct.
1912 phase->_igvn.replace_node(cl->phi(), cl->init_trip());
1913 phase->C->set_major_progress();
1914 return true;
1915 }
1849 1916
1850 //============================================================================= 1917 //=============================================================================
1851 //------------------------------iteration_split_impl--------------------------- 1918 //------------------------------iteration_split_impl---------------------------
1852 bool IdealLoopTree::iteration_split_impl( PhaseIdealLoop *phase, Node_List &old_new ) { 1919 bool IdealLoopTree::iteration_split_impl( PhaseIdealLoop *phase, Node_List &old_new ) {
1920 // Compute exact loop trip count if possible.
1921 compute_exact_trip_count(phase);
1922
1923 // Convert one iteration loop into normal code.
1924 if (policy_do_one_iteration_loop(phase))
1925 return true;
1926
1853 // Check and remove empty loops (spam micro-benchmarks) 1927 // Check and remove empty loops (spam micro-benchmarks)
1854 if( policy_do_remove_empty_loop(phase) ) 1928 if (policy_do_remove_empty_loop(phase))
1855 return true; // Here we removed an empty loop 1929 return true; // Here we removed an empty loop
1856 1930
1857 bool should_peel = policy_peeling(phase); // Should we peel? 1931 bool should_peel = policy_peeling(phase); // Should we peel?
1858 1932
1859 bool should_unswitch = policy_unswitching(phase); 1933 bool should_unswitch = policy_unswitching(phase);
1860 1934
1861 // Non-counted loops may be peeled; exactly 1 iteration is peeled. 1935 // Non-counted loops may be peeled; exactly 1 iteration is peeled.
1862 // This removes loop-invariant tests (usually null checks). 1936 // This removes loop-invariant tests (usually null checks).
1863 if( !_head->is_CountedLoop() ) { // Non-counted loop 1937 if (!_head->is_CountedLoop()) { // Non-counted loop
1864 if (PartialPeelLoop && phase->partial_peel(this, old_new)) { 1938 if (PartialPeelLoop && phase->partial_peel(this, old_new)) {
1865 // Partial peel succeeded so terminate this round of loop opts 1939 // Partial peel succeeded so terminate this round of loop opts
1866 return false; 1940 return false;
1867 } 1941 }
1868 if( should_peel ) { // Should we peel? 1942 if (should_peel) { // Should we peel?
1869 #ifndef PRODUCT 1943 #ifndef PRODUCT
1870 if (PrintOpto) tty->print_cr("should_peel"); 1944 if (PrintOpto) tty->print_cr("should_peel");
1871 #endif 1945 #endif
1872 phase->do_peeling(this,old_new); 1946 phase->do_peeling(this,old_new);
1873 } else if( should_unswitch ) { 1947 } else if (should_unswitch) {
1874 phase->do_unswitching(this, old_new); 1948 phase->do_unswitching(this, old_new);
1875 } 1949 }
1876 return true; 1950 return true;
1877 } 1951 }
1878 CountedLoopNode *cl = _head->as_CountedLoop(); 1952 CountedLoopNode *cl = _head->as_CountedLoop();
1879 1953
1880 if( !cl->loopexit() ) return true; // Ignore various kinds of broken loops 1954 if (!cl->loopexit()) return true; // Ignore various kinds of broken loops
1881 1955
1882 // Do nothing special to pre- and post- loops 1956 // Do nothing special to pre- and post- loops
1883 if( cl->is_pre_loop() || cl->is_post_loop() ) return true; 1957 if (cl->is_pre_loop() || cl->is_post_loop()) return true;
1884 1958
1885 // Compute loop trip count from profile data 1959 // Compute loop trip count from profile data
1886 compute_profile_trip_cnt(phase); 1960 compute_profile_trip_cnt(phase);
1887 1961
1888 // Before attempting fancy unrolling, RCE or alignment, see if we want 1962 // Before attempting fancy unrolling, RCE or alignment, see if we want
1889 // to completely unroll this loop or do loop unswitching. 1963 // to completely unroll this loop or do loop unswitching.
1890 if( cl->is_normal_loop() ) { 1964 if (cl->is_normal_loop()) {
1891 if (should_unswitch) { 1965 if (should_unswitch) {
1892 phase->do_unswitching(this, old_new); 1966 phase->do_unswitching(this, old_new);
1893 return true; 1967 return true;
1894 } 1968 }
1895 bool should_maximally_unroll = policy_maximally_unroll(phase); 1969 bool should_maximally_unroll = policy_maximally_unroll(phase);
1896 if( should_maximally_unroll ) { 1970 if (should_maximally_unroll) {
1897 // Here we did some unrolling and peeling. Eventually we will 1971 // Here we did some unrolling and peeling. Eventually we will
1898 // completely unroll this loop and it will no longer be a loop. 1972 // completely unroll this loop and it will no longer be a loop.
1899 phase->do_maximally_unroll(this,old_new); 1973 phase->do_maximally_unroll(this,old_new);
1900 return true; 1974 return true;
1901 } 1975 }
1935 bool may_rce_align = !policy_peel_only(phase) || should_rce || should_align; 2009 bool may_rce_align = !policy_peel_only(phase) || should_rce || should_align;
1936 2010
1937 // If we have any of these conditions (RCE, alignment, unrolling) met, then 2011 // If we have any of these conditions (RCE, alignment, unrolling) met, then
1938 // we switch to the pre-/main-/post-loop model. This model also covers 2012 // we switch to the pre-/main-/post-loop model. This model also covers
1939 // peeling. 2013 // peeling.
1940 if( should_rce || should_align || should_unroll ) { 2014 if (should_rce || should_align || should_unroll) {
1941 if( cl->is_normal_loop() ) // Convert to 'pre/main/post' loops 2015 if (cl->is_normal_loop()) // Convert to 'pre/main/post' loops
1942 phase->insert_pre_post_loops(this,old_new, !may_rce_align); 2016 phase->insert_pre_post_loops(this,old_new, !may_rce_align);
1943 2017
1944 // Adjust the pre- and main-loop limits to let the pre and post loops run 2018 // Adjust the pre- and main-loop limits to let the pre and post loops run
1945 // with full checks, but the main-loop with no checks. Remove said 2019 // with full checks, but the main-loop with no checks. Remove said
1946 // checks from the main body. 2020 // checks from the main body.
1947 if( should_rce ) 2021 if (should_rce)
1948 phase->do_range_check(this,old_new); 2022 phase->do_range_check(this,old_new);
1949 2023
1950 // Double loop body for unrolling. Adjust the minimum-trip test (will do 2024 // Double loop body for unrolling. Adjust the minimum-trip test (will do
1951 // twice as many iterations as before) and the main body limit (only do 2025 // twice as many iterations as before) and the main body limit (only do
1952 // an even number of trips). If we are peeling, we might enable some RCE 2026 // an even number of trips). If we are peeling, we might enable some RCE
1953 // and we'd rather unroll the post-RCE'd loop SO... do not unroll if 2027 // and we'd rather unroll the post-RCE'd loop SO... do not unroll if
1954 // peeling. 2028 // peeling.
1955 if( should_unroll && !should_peel ) 2029 if (should_unroll && !should_peel)
1956 phase->do_unroll(this,old_new, true); 2030 phase->do_unroll(this,old_new, true);
1957 2031
1958 // Adjust the pre-loop limits to align the main body 2032 // Adjust the pre-loop limits to align the main body
1959 // iterations. 2033 // iterations.
1960 if( should_align ) 2034 if (should_align)
1961 Unimplemented(); 2035 Unimplemented();
1962 2036
1963 } else { // Else we have an unchanged counted loop 2037 } else { // Else we have an unchanged counted loop
1964 if( should_peel ) // Might want to peel but do nothing else 2038 if (should_peel) // Might want to peel but do nothing else
1965 phase->do_peeling(this,old_new); 2039 phase->do_peeling(this,old_new);
1966 } 2040 }
1967 return true; 2041 return true;
1968 } 2042 }
1969 2043