Re: [PATCH] [RFA] [PR tree-optmization/69740] Schedule loop fixups when needed

[Richard Biener <richard dot guenther at gmail dot com>]

On Thu, Feb 25, 2016 at 7:18 AM, Jeff Law <law@redhat.com> wrote:
>
> PR69740 shows two instances where one or more transformations ultimately
> lead to the removal of a basic block.
>
> In both cases, removal of the basic block removes a path into an irreducible
> region and turns the irreducible region into a natural loop.
>
> When that occurs we need to be requesting loops to be fixed up.
>
> My first patch was to handle this is was in tree-ssa-dce.c and that fixed
> the initial problem report.  As I was cobbling the patch together, I
> pondered putting the changes into delete_basic_block because that would
> capture other instances of this problem.
>
> When I looked at the second instance, it came via a completely different
> path (tail merging).  Again it was a case where we called delete_basic_block
> which in turn changed an irreducible region into a natural loop.  So I
> tossed my original patch and put the test into delete_basic_block as you see
> here.
>
> Bootstrapped and regression tested on x86_64-linux-gnu.  OK for the trunk
> and the gcc-5 branch after a suitable soak time?
>
>
>
> Jeff
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 913abc8..42e5b4f 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,10 @@
> +2016-02-24  Jeff Law  <law@redhat.com>
> +
> +       PR tree-optimization/69740
> +       * cfghooks.c (delete_basic_block): Request loop fixups if we delete
> +       a block with an outgoing edge to a block marked as being in anx
> +       irreducible region.
> +
>  2016-02-24  Jason Merrill  <jason@redhat.com>
>
>         * common.opt (flifetime-dse): Add -flifetime-dse=1.
> diff --git a/gcc/cfghooks.c b/gcc/cfghooks.c
> index bbb1017..4d31aa9 100644
> --- a/gcc/cfghooks.c
> +++ b/gcc/cfghooks.c
> @@ -574,6 +574,14 @@ delete_basic_block (basic_block bb)
>    if (!cfg_hooks->delete_basic_block)
>      internal_error ("%s does not support delete_basic_block",
> cfg_hooks->name);
>
> +  /* Look at BB's successors, if any are marked as BB_IRREDUCIBLE_LOOP,
> then
> +     removing BB (and its outgoing edges) may make the loop a natural
> +     loop.  In which case we need to schedule loop fixups.  */
> +  if (current_loops)
> +    for (edge_iterator ei = ei_start (bb->succs); !ei_end_p (ei); ei_next
> (&ei))
> +      if (ei_edge (ei)->dest->flags & BB_IRREDUCIBLE_LOOP)
> +       loops_state_set (LOOPS_NEED_FIXUP);

So I fail to see how only successor edges are relevant.  Isn't the important
case to catch whether we remove an edge marked EDGE_IRREDUCIBLE_LOOP?
Even if the BB persists we might have exposed a new loop here.

Note that it is not safe to look at {BB,EDGE}_IRREDUCIBLE_LOOP if the loop
state does not have LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS set
(the flags may be stale or missing).  So it might be that we can't rely on
non-loop passes modifying the CFG to handle this optimistically.

Thus, how about (my main point) moving this to remove_edge instead, like

Index: gcc/cfghooks.c
===================================================================
--- gcc/cfghooks.c      (revision 233693)
+++ gcc/cfghooks.c      (working copy)
@@ -408,7 +408,15 @@ void
 remove_edge (edge e)
 {
   if (current_loops != NULL)
-    rescan_loop_exit (e, false, true);
+    {
+      rescan_loop_exit (e, false, true);
+      /* If we remove an edge that is part of an irreducible region
+         or we remove an entry into an irreducible region we may expose
+        new natural loops.  */
+      if (e->flags & EDGE_IRREDUCIBLE_LOOP
+         || e->dest->flags & BB_IRREDUCIBLE_LOOP)
+       loops_state_set (LOOPS_NEED_FIXUP);
+    }

   /* This is probably not needed, but it doesn't hurt.  */
   /* FIXME: This should be called via a remove_edge hook.  */

that then handles delete_basic_block via its call to remove all
incoming/outgoing edges.

As for the comment above it may need to be conservatively

   if (! loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
      || checks above)

That looks like a more complete fix (and it avoids an extra loop over
all edges).

(the edge flag check might be redundant given it's only set if both
src and dest are
BB_IRREDUCIBLE_LOOP).

Richard.

>    cfg_hooks->delete_basic_block (bb);
>
>    if (current_loops != NULL)
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index 311232f..b0df819 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,9 @@
> +2016-02-04  Jeff Law  <law@redhat.com>
> +
> +       PR tree-optimization/69740
> +       * gcc.c-torture/compile/pr69740-1.c: New test.
> +       * gcc.c-torture/compile/pr69740-2.c: New test.
> +
>  2016-02-24  Martin Sebor  <msebor@redhat.com>
>
>         PR c++/69912
> diff --git a/gcc/testsuite/gcc.c-torture/compile/pr69740-1.c
> b/gcc/testsuite/gcc.c-torture/compile/pr69740-1.c
> new file mode 100644
> index 0000000..ac867d8
> --- /dev/null
> +++ b/gcc/testsuite/gcc.c-torture/compile/pr69740-1.c
> @@ -0,0 +1,12 @@
> +char a;
> +short b;
> +void fn1() {
> +  if (b)
> +    ;
> +  else {
> +    int c[1] = {0};
> +  l1:;
> +  }
> +  if (a)
> +    goto l1;
> +}
> diff --git a/gcc/testsuite/gcc.c-torture/compile/pr69740-2.c
> b/gcc/testsuite/gcc.c-torture/compile/pr69740-2.c
> new file mode 100644
> index 0000000..a89c9a0
> --- /dev/null
> +++ b/gcc/testsuite/gcc.c-torture/compile/pr69740-2.c
> @@ -0,0 +1,19 @@
> +inline int foo(int *p1, int p2) {
> +  int z = *p1;
> +  while (z > p2)
> +    p2 = 2;
> +  return z;
> +}
> +int main() {
> +  int i;
> +  for (;;) {
> +    int j, k;
> +    i = foo(&k, 7);
> +    if (k)
> +      j = i;
> +    else
> +      k = j;
> +    if (2 != j)
> +      __builtin_abort();
> +  }
> +}
>