[RFA,PR,tree-optmization/69740] Schedule loop fixups when needed
diff mbox

Message ID CAFiYyc0Sr8kJ5Kjxp6mcG276f2yf7aaLqHdE56h2H-YPZBHsoQ@mail.gmail.com
State New
Headers show

Commit Message

Richard Biener Feb. 25, 2016, 10 a.m. UTC
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


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();
> +  }
> +}
>

Comments

Jeff Law Feb. 25, 2016, 3:59 p.m. UTC | #1
On 02/25/2016 03:00 AM, Richard Biener wrote:

>> +  /* 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.
Yea, let me give that a spin.

>
> 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.
I was concerned about this as well.   The problem case would be if we 
have an irreducible loop with nodes not marked.  In that case we could 
fail to ask for loop fixups leading to failure again.  The other cases 
shouldn't cause failures, but can cause us to spend time fixing up loops 
which perhaps we didn't need to.

Anyway, I'll have a closer look at that too.



Jeff

Patch
diff mbox

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.  */