Fix handling of static exists in loop_ch

This patch fixes wrong return value in should_duplicate_loop_header_p.
Doing so uncovered suboptimal decisions on some jump threading testcases
where we choose 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 choose 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.

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 b49d1fc9576ec0422333d870fd8803154bb5de7d..11ee29458a2e1b42aa2e275e039fff176d2e9747 100644 (file)
--- 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 6cdb87a762fad983021db4360a1a5ce6ab033a81..461416e40862061cf326f0b75e94974dd936db30 100644 (file)
--- 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,