> We seem to peel one iteration for no good reason. The loop is > a do-while loop already. The key is we see the first iteration > exit condition is known not taken and then: Hi, this is patch fixing wrong return value in should_duplicate_loop_header_p. Doing so uncovered suboptimal decisions on some jump threading testcases where we chose to stop duplicating just before basic block that has zero cost and duplicating so would be always a win.
This is because the heuristics trying to chose right point to duplicate all winning blocks and to get loop to be do_while did not account zero_cost blocks in all cases. The patch simplifies the logic by simply remembering zero cost blocks and handling them last after the right stopping point is chosen. Bootstrapped/regtested x86_64-linux, OK? gcc/ChangeLog: * tree-ssa-loop-ch.cc (enum ch_decision): Fix comment. (should_duplicate_loop_header_p): Fix return value for static exits. (ch_base::copy_headers): Improve handling of ch_possible_zero_cost. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/copy-headers-9.c: Update template. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-9.c b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-9.c index b49d1fc9576..11ee29458a2 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-9.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-9.c @@ -13,7 +13,6 @@ void test (int m, int n) } while (i<10); } -/* { dg-final { scan-tree-dump-times "Duplicating bb . is a win" 2 "ch2" } } */ -/* { dg-final { scan-tree-dump-times "Duplicating bb . is a win. it has zero" 1 "ch2" } } */ +/* { dg-final { scan-tree-dump-times "Duplicating bb . is a win" 1 "ch2" } } */ /* { dg-final { scan-tree-dump-times "Will duplicate bb" 2 "ch2" } } */ /* { dg-final { scan-tree-dump "is now do-while loop" "ch2" } } */ diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc index 6cdb87a762f..461416e4086 100644 --- a/gcc/tree-ssa-loop-ch.cc +++ b/gcc/tree-ssa-loop-ch.cc @@ -176,7 +176,7 @@ enum ch_decision ch_impossible, /* We can copy it if it enables wins. */ ch_possible, - /* We can "cop" it if it enables wins and doing + /* We can "copy" it if it enables wins and doing so will introduce no new code. */ ch_possible_zero_cost, /* We want to copy. */ @@ -464,7 +464,7 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop, TODO: Even if duplication costs some size we may opt to do so in case exit probability is significant enough (do partial peeling). */ if (static_exit) - return code_size_cost ? ch_possible_zero_cost : ch_win; + return !code_size_cost ? ch_possible_zero_cost : ch_possible; /* We was not able to prove that conditional will be eliminated. */ int insns = estimate_num_insns (last, &eni_size_weights); @@ -824,6 +824,7 @@ ch_base::copy_headers (function *fun) int last_win_nheaders = 0; bool last_win_invariant_exit = false; ch_decision ret; + auto_vec <ch_decision, 32> decision; hash_set <edge> *invariant_exits = new hash_set <edge>; hash_set <edge> *static_exits = new hash_set <edge>; while ((ret = should_duplicate_loop_header_p (header, loop, ranger, @@ -833,6 +834,7 @@ ch_base::copy_headers (function *fun) != ch_impossible) { nheaders++; + decision.safe_push (ret); if (ret >= ch_win) { last_win_nheaders = nheaders; @@ -841,20 +843,6 @@ ch_base::copy_headers (function *fun) fprintf (dump_file, " Duplicating bb %i is a win\n", header->index); } - /* Duplicate BB if has zero cost but be sure it will not - imply duplication of other BBs. */ - else if (ret == ch_possible_zero_cost - && (last_win_nheaders == nheaders - 1 - || (last_win_nheaders == nheaders - 2 - && last_win_invariant_exit))) - { - last_win_nheaders = nheaders; - last_win_invariant_exit = false; - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, - " Duplicating bb %i is a win; it has zero cost\n", - header->index); - } else if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " May duplicate bb %i\n", header->index); @@ -884,6 +872,16 @@ ch_base::copy_headers (function *fun) fprintf (dump_file, " Duplicating header BB to obtain do-while loop\n"); } + /* "Duplicate" all BBs with zero cost following last basic blocks we + decided to copy. */ + while (last_win_nheaders < (int)decision.length () + && decision[last_win_nheaders] == ch_possible_zero_cost) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + " Duplicating extra bb is a win; it has zero cost\n"); + last_win_nheaders++; + } if (last_win_nheaders) candidates.safe_push ({loop, last_win_nheaders,