loop-ch improvements, part 5

Currently loop-ch skips all do-while loops.  But when loop is not do-while
in addition to original goal of turining it to do-while it can do additional
things:
 1) move out loop invariant computations
 2) duplicate loop invariant conditionals and eliminate them in loop body.
 3) prove that some exits are always true in first iteration
    and can be skipped

Most of time 1 can be done by lim (exception is when the invariant computation
is conditional). For 2 we however don't really have other place doing it except
for loop unswitching that is more expensive (it will duplicate the loop and
then optimize out one path to non-loop).
3 can be done by loop peeling but it is also more expensive by duplicating full
loop body.

This patch improves heuristics by not giving up on do-while loops and trying
to find sequence of BBs to duplicate to obtain one of goals:
 - turn loop to do-while
 - eliminate invariant conditional in loop body
 - do partial "peeling" as long as code optimizes enough so this does not
   increase code size.

Bootstrapped/regtested x86_64-linux, OK?

gcc/ChangeLog:

	* tree-ssa-loop-ch.cc (enum ch_decision): New enum.
	(should_duplicate_loop_header_p): Return info on profitability.
	(do_while_loop_p): Watch for constant conditionals.
	(update_profile_after_ch): Do not sanity check that all
	static exits are taken.
	(ch_base::copy_headers): Run on all loops.
	(pass_ch::process_loop_p): Improve heuristics by handling also
	do_while loop and duplicating shortest sequence containing all
	winning blocks.

gcc/testsuite/ChangeLog:

	* gcc.dg/loop-unswitch-17.c: Disable ch.
	* gcc.dg/pr103079.c: Disable ch.
	* gcc.dg/tree-ssa/copy-headers-7.c: Update so ch behaves
	as expected.
	* gcc.dg/tree-ssa/copy-headers.c: Update template.
	* gcc.dg/tree-ssa/copy-headers-9.c: New test.

diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-17.c b/gcc/testsuite/gcc.dg/loop-unswitch-17.c
index 8655e09a51c2f8cb86e2f240fc28985b674f129d..4b806c475b1c32c8ab1ff148dabc04f696941360 100644 (file)
--- a/gcc/testsuite/gcc.dg/loop-unswitch-17.c
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-17.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-optimized" } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-optimized -fno-tree-ch" } */
 
 int foo (int a)
 {

diff --git a/gcc/testsuite/gcc.dg/pr103079.c b/gcc/testsuite/gcc.dg/pr103079.c
index 7f6632fc6693fb988e1c0f66155a54af4c86a5b5..7b1075447256488cff608b9fe40a4d0c26ca9a8d 100644 (file)
--- a/gcc/testsuite/gcc.dg/pr103079.c
+++ b/gcc/testsuite/gcc.dg/pr103079.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-Os -fdump-tree-vrp2" } */
+/* { dg-options "-Os -fdump-tree-vrp2 -fno-tree-ch" } */
 
 int a, b = -2;
 int main() {

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-7.c b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-7.c
index e2a6c75f2e90aa8b6c1c682fd003c27fbf37804c..b3df3b6398e5cc4f253a2275b869ea3fcf5b0270 100644 (file)
--- a/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-7.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-7.c
@@ -4,7 +4,7 @@
 int is_sorted(int *a, int n, int m, int k)
 {
   if (k > 0)
-    for (int i = 0; i < n - 1 && m && k > i; i++)
+    for (int i = 0; k > i && m && i < n - 1 ; i++)
       if (a[i] > a[i + 1])
        return 0;
   return 1;
@@ -17,5 +17,4 @@ int is_sorted(int *a, int n, int m, int k)
 /* { dg-final { scan-tree-dump-times "Conditional combines static and invariant" 0 "ch2" } } */
 /* { dg-final { scan-tree-dump-times "Will elliminate invariant exit" 1 "ch2" } } */
 /* { dg-final { scan-tree-dump-times "Will eliminate peeled conditional" 1 "ch2" } } */
-/* { dg-final { scan-tree-dump-times "Not duplicating bb .: condition based on non-IV loop variant." 1 "ch2" } } */
 /* { dg-final { scan-tree-dump-times "Will duplicate bb" 3 "ch2" } } */

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-9.c b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-9.c
new file mode 100644 (file)
index 0000000..7cc162c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-9.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ch-details" } */
+int a[100];
+void test (int m, int n)
+{
+       int i = 0;
+       do
+       {
+               if (m)
+                       break;
+               i++;
+               a[i]=0;
+       }
+       while (i<10);
+}
+/* { dg-final { scan-tree-dump-times "Duplicating bb . is a win" 1 "ch2" } } */
+/* { dg-final { scan-tree-dump-times "May duplicate bb" 1 "ch2" } } */
+/* { dg-final { scan-tree-dump-times "Duplicating additional BB to obtain do-while loop" 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/testsuite/gcc.dg/tree-ssa/copy-headers.c b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers.c
index a5a82121ff293415e60077d99b5fa469c7f1aadf..f4f2b2aa70bdaf6598211625f32a462c6a397ae0 100644 (file)
--- a/gcc/testsuite/gcc.dg/tree-ssa/copy-headers.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers.c
@@ -12,4 +12,4 @@ void bla (void)
 }
 
 /* There should be a header duplicated.  */
-/* { dg-final { scan-tree-dump-times "Duplicating header" 1 "ch2"} } */
+/* { dg-final { scan-tree-dump-times "Duplicating header of the" 1 "ch2"} } */

diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc
index a87ebc58e3d7bc2f4048245fcdf125def2f091a0..6cdb87a762fad983021db4360a1a5ce6ab033a81 100644 (file)
--- a/gcc/tree-ssa-loop-ch.cc
+++ b/gcc/tree-ssa-loop-ch.cc
@@ -168,11 +168,28 @@ loop_combined_static_and_iv_p (class loop *loop,
   return gimple_uid (SSA_NAME_DEF_STMT (op)) & 4;
 }
 
+/* Decision about posibility of copying a given header.  */
+
+enum ch_decision
+{
+  /* We do not want to copy this header.  */
+  ch_impossible,
+  /* We can copy it if it enables wins.  */
+  ch_possible,
+  /* We can "cop" it if it enables wins and doing
+     so will introduce no new code.  */
+  ch_possible_zero_cost,
+  /* We want to copy.  */
+  ch_win,
+  /* We want to copy and we will eliminate loop exit.  */
+  ch_win_invariant_exit
+};
+
 /* Check whether we should duplicate HEADER of LOOP.  At most *LIMIT
    instructions should be duplicated, limit is decreased by the actual
    amount.  */
 
-static bool
+static ch_decision
 should_duplicate_loop_header_p (basic_block header, class loop *loop,
                                gimple_ranger *ranger,
                                int *limit,
@@ -190,7 +207,7 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop,
        fprintf (dump_file,
                 "  Not duplicating bb %i: it is single succ.\n",
                 header->index);
-      return false;
+      return ch_impossible;
     }
 
   if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
@@ -200,7 +217,7 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop,
        fprintf (dump_file,
                 "  Not duplicating bb %i: both successors are in loop.\n",
                 loop->num);
-      return false;
+      return ch_impossible;
     }
 
   /* If this is not the original loop header, we want it to have just
@@ -211,7 +228,7 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop,
        fprintf (dump_file,
                 "  Not duplicating bb %i: it has mutiple predecestors.\n",
                 header->index);
-      return false;
+      return ch_impossible;
     }
 
   gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (header));
@@ -221,7 +238,7 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop,
        fprintf (dump_file,
                 "  Not duplicating bb %i: it does not end by conditional.\n",
                 header->index);
-      return false;
+      return ch_impossible;
     }
 
   path_range_query *query = NULL;
@@ -233,6 +250,7 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop,
                                            query, psi.phi ());
        gimple_set_uid (psi.phi (), static_p ? 2 : 0);
       }
+  bool code_size_cost = false;
 
   /* Count number of instructions and punt on calls.
      Populate stmts INV flag to later apply heuristics to the
@@ -268,7 +286,7 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop,
                     header->index);
          if (query)
            delete query;
-         return false;
+         return ch_impossible;
        }
 
       /* Classify the stmt is invariant in the loop.  */
@@ -343,6 +361,8 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop,
 
       int insns = estimate_num_insns (last, &eni_size_weights);
       *limit -= insns;
+      if (insns)
+       code_size_cost = true;
       if (dump_file && (dump_flags & TDF_DETAILS))
        fprintf (dump_file,
                 "    Acconting stmt as %i insns\n", insns);
@@ -354,7 +374,7 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop,
                     header->index);
          if (query)
            delete query;
-         return false;
+         return ch_impossible;
        }
     }
 
@@ -403,7 +423,7 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop,
       if (dump_file && (dump_flags & TDF_DETAILS))
        fprintf (dump_file,
                 "  Conditional combines static and invariant op.\n");
-     return true;
+     return ch_win;
    }
 
   edge static_exit = static_loop_exit (loop, header, *ranger, query);
@@ -435,11 +455,16 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop,
                invariant_exits->add (e);
              }
        }
-      return true;
+      return ch_win_invariant_exit;
     }
 
+  /* If the static exit fully optimize out, it is win to "duplicate"
+     it.
+
+     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 true;
+    return code_size_cost ? ch_possible_zero_cost : ch_win;
 
   /* We was not able to prove that conditional will be eliminated.  */
   int insns = estimate_num_insns (last, &eni_size_weights);
@@ -453,19 +478,10 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop,
        fprintf (dump_file,
                 "  Not duplicating bb %i contains too many insns.\n",
                 header->index);
-      return false;
-    }
-
-  if (header != loop->header)
-    {
-      if (dump_file && (dump_flags & TDF_DETAILS))
-       fprintf (dump_file,
-                "  Not duplicating bb %i: condition based on non-IV loop"
-                " variant.\n", header->index);
-      return false;
+      return ch_impossible;
     }
 
-  return true;
+  return ch_possible;
 }
 
 /* Checks whether LOOP is a do-while style loop.  */
@@ -496,10 +512,11 @@ do_while_loop_p (class loop *loop)
                 "predecessors.\n", loop->num);
       return false;
     }
+  basic_block pred = single_pred (loop->latch);
 
   /* If the latch predecessor doesn't exit the loop, it is not a
      do-while loop.  */
-  if (!loop_exits_from_bb_p (loop, single_pred (loop->latch)))
+  if (!loop_exits_from_bb_p (loop, pred))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
        fprintf (dump_file,
@@ -507,6 +524,18 @@ do_while_loop_p (class loop *loop)
                 "does not exit loop.\n", loop->num);
       return false;
     }
+  gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (pred));
+  if (last
+      && (gimple_cond_lhs (last) == boolean_false_node
+         || gimple_cond_lhs (last) == boolean_true_node)
+      && gimple_cond_rhs (last) == boolean_false_node)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+       fprintf (dump_file,
+                "Loop %i is not do-while loop: latch predecessor "
+                "contains exit we optimized out.\n", loop->num);
+      return false;
+    }
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "Loop %i is do-while loop\n", loop->num);
@@ -634,9 +663,9 @@ update_profile_after_ch (class loop *loop,
        }
       entry_count = e_copy->count ();
     }
-  /* Be sure that we seen all edges we are supposed to update.  */
-  gcc_checking_assert (static_exits->is_empty ()
-                      && invariant_exits->is_empty ());
+  /* Be sure that we seen all invariant exit edges we are supposed to update.
+     We may have recorded some static exists we decided to not duplicate.  */
+  gcc_checking_assert (invariant_exits->is_empty ());
 }
 
 namespace {
@@ -792,16 +821,43 @@ ch_base::copy_headers (function *fun)
         the header to have just a single successor and copying up to
         postdominator.  */
       int nheaders = 0;
+      int last_win_nheaders = 0;
+      bool last_win_invariant_exit = false;
+      ch_decision ret;
       hash_set <edge> *invariant_exits = new hash_set <edge>;
       hash_set <edge> *static_exits = new hash_set <edge>;
-      while (should_duplicate_loop_header_p (header, loop, ranger,
-                                            &remaining_limit,
-                                            invariant_exits,
-                                            static_exits))
+      while ((ret = should_duplicate_loop_header_p (header, loop, ranger,
+                                                   &remaining_limit,
+                                                   invariant_exits,
+                                                   static_exits))
+            != ch_impossible)
        {
          nheaders++;
-         if (dump_file && (dump_flags & TDF_DETAILS))
-           fprintf (dump_file, "    Will duplicate bb %i\n", header->index);
+         if (ret >= ch_win)
+           {
+             last_win_nheaders = nheaders;
+             last_win_invariant_exit = (ret == ch_win_invariant_exit);
+             if (dump_file && (dump_flags & TDF_DETAILS))
+               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);
 
          /* Find a successor of header that is inside a loop; i.e. the new
             header after the condition is copied.  */
@@ -811,8 +867,27 @@ ch_base::copy_headers (function *fun)
            header = EDGE_SUCC (header, 1)->dest;
        }
 
-      if (nheaders)
-       candidates.safe_push ({loop, nheaders, invariant_exits, static_exits});
+      /* Try to turn loop into do-while.  This means ensuring that
+        last duplicated header will not have loop invariant exit.  */
+      if (last_win_nheaders && last_win_invariant_exit
+         && nheaders > last_win_nheaders)
+       {
+         last_win_nheaders++;
+         if (dump_file && (dump_flags & TDF_DETAILS))
+           fprintf (dump_file,
+                    "    Duplicating additional BB to obtain do-while loop\n");
+       }
+      else if (!last_win_nheaders && nheaders && !do_while_loop_p (loop))
+       {
+         last_win_nheaders = 1;
+         if (dump_file && (dump_flags & TDF_DETAILS))
+           fprintf (dump_file,
+                    "    Duplicating header BB to obtain do-while loop\n");
+       }
+
+      if (last_win_nheaders)
+       candidates.safe_push ({loop, last_win_nheaders,
+                             invariant_exits, static_exits});
       else
        {
          delete invariant_exits;
@@ -844,6 +919,8 @@ ch_base::copy_headers (function *fun)
          entry_count += e->count ();
       while (n_bbs < candidate.nheaders)
        {
+           if (dump_file && (dump_flags & TDF_DETAILS))
+             fprintf (dump_file, "    Will duplicate bb %i\n", header->index);
          /* Find a successor of header that is inside a loop; i.e. the new
             header after the condition is copied.  */
          if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
@@ -1111,9 +1188,9 @@ pass_ch_vect::execute (function *fun)
 /* Apply header copying according to a very simple test of do-while shape.  */
 
 bool
-pass_ch::process_loop_p (class loop *loop)
+pass_ch::process_loop_p (class loop *)
 {
-  return !do_while_loop_p (loop);
+  return true;
 }
 
 /* Apply header-copying to loops where we might enable vectorization.  */