[PATCH] Free dominance info at the beginning of pass_jump_after_combine

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

[PATCH] Free dominance info at the beginning of pass_jump_after_combine

Ilya Leoshkevich
Bootstrapped and regtested on x86_64-redhat-linux, s390x-redhat-linux
and ppc64le-redhat-linux.  OK for trunk and gcc-9-branch?

try_forward_edges does not update dominance info, and merge_blocks
relies on it being up-to-date.  In PR92430 stale dominance info makes
merge_blocks produce a loop in the dominator tree, which in turn makes
delete_basic_block loop forever.

Fix by freeing dominance info at the beginning of cleanup_cfg.

gcc/ChangeLog:

2019-11-12  Ilya Leoshkevich  <[hidden email]>

        PR rtl-optimization/92430
        * cfgcleanup.c (pass_jump_after_combine::execute): Free
        dominance info at the beginning.

gcc/testsuite/ChangeLog:

2019-11-12  Ilya Leoshkevich  <[hidden email]>

        PR rtl-optimization/92430
        * gcc.dg/pr92430.c: New test (from Arseny Solokha).
---
 gcc/cfgcleanup.c               |  3 +++
 gcc/testsuite/gcc.dg/pr92430.c | 25 +++++++++++++++++++++++++
 2 files changed, 28 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/pr92430.c

diff --git a/gcc/cfgcleanup.c b/gcc/cfgcleanup.c
index 835f7d79ea4..20096de88b4 100644
--- a/gcc/cfgcleanup.c
+++ b/gcc/cfgcleanup.c
@@ -3312,6 +3312,9 @@ public:
 unsigned int
 pass_jump_after_combine::execute (function *)
 {
+  /* Jump threading does not keep dominators up-to-date.  */
+  free_dominance_info (CDI_DOMINATORS);
+  free_dominance_info (CDI_POST_DOMINATORS);
   cleanup_cfg (flag_thread_jumps ? CLEANUP_THREADING : 0);
   return 0;
 }
diff --git a/gcc/testsuite/gcc.dg/pr92430.c b/gcc/testsuite/gcc.dg/pr92430.c
new file mode 100644
index 00000000000..915606893ba
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr92430.c
@@ -0,0 +1,25 @@
+// PR rtl-optimization/92430
+// { dg-do compile }
+// { dg-options "-Os -fno-if-conversion -fno-tree-dce -fno-tree-loop-optimize -fno-tree-vrp" }
+
+int eb, ko;
+
+void
+e9 (int pe, int lx)
+{
+  int ir;
+
+  for (ir = 0; ir < 1; ++ir)
+    {
+      for (ko = 0; ko < 1; ++ko)
+        {
+          for (eb = 0; eb < 1; ++eb)
+            ko += pe;
+
+          for (ko = 0; ko < 1; ++ko)
+            ;
+        }
+
+      pe = ir = lx;
+    }
+}
--
2.23.0

Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Free dominance info at the beginning of pass_jump_after_combine

Richard Biener
On Tue, 12 Nov 2019, Ilya Leoshkevich wrote:

> Bootstrapped and regtested on x86_64-redhat-linux, s390x-redhat-linux
> and ppc64le-redhat-linux.  OK for trunk and gcc-9-branch?
>
> try_forward_edges does not update dominance info, and merge_blocks
> relies on it being up-to-date.  In PR92430 stale dominance info makes
> merge_blocks produce a loop in the dominator tree, which in turn makes
> delete_basic_block loop forever.
>
> Fix by freeing dominance info at the beginning of cleanup_cfg.

You can omit freeing CDI_POST_DOMINATORS, those are never kept
across passes.

OK with that change.

Richard.

> gcc/ChangeLog:
>
> 2019-11-12  Ilya Leoshkevich  <[hidden email]>
>
> PR rtl-optimization/92430
> * cfgcleanup.c (pass_jump_after_combine::execute): Free
> dominance info at the beginning.
>
> gcc/testsuite/ChangeLog:
>
> 2019-11-12  Ilya Leoshkevich  <[hidden email]>
>
> PR rtl-optimization/92430
> * gcc.dg/pr92430.c: New test (from Arseny Solokha).
> ---
>  gcc/cfgcleanup.c               |  3 +++
>  gcc/testsuite/gcc.dg/pr92430.c | 25 +++++++++++++++++++++++++
>  2 files changed, 28 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/pr92430.c
>
> diff --git a/gcc/cfgcleanup.c b/gcc/cfgcleanup.c
> index 835f7d79ea4..20096de88b4 100644
> --- a/gcc/cfgcleanup.c
> +++ b/gcc/cfgcleanup.c
> @@ -3312,6 +3312,9 @@ public:
>  unsigned int
>  pass_jump_after_combine::execute (function *)
>  {
> +  /* Jump threading does not keep dominators up-to-date.  */
> +  free_dominance_info (CDI_DOMINATORS);
> +  free_dominance_info (CDI_POST_DOMINATORS);
>    cleanup_cfg (flag_thread_jumps ? CLEANUP_THREADING : 0);
>    return 0;
>  }
> diff --git a/gcc/testsuite/gcc.dg/pr92430.c b/gcc/testsuite/gcc.dg/pr92430.c
> new file mode 100644
> index 00000000000..915606893ba
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr92430.c
> @@ -0,0 +1,25 @@
> +// PR rtl-optimization/92430
> +// { dg-do compile }
> +// { dg-options "-Os -fno-if-conversion -fno-tree-dce -fno-tree-loop-optimize -fno-tree-vrp" }
> +
> +int eb, ko;
> +
> +void
> +e9 (int pe, int lx)
> +{
> +  int ir;
> +
> +  for (ir = 0; ir < 1; ++ir)
> +    {
> +      for (ko = 0; ko < 1; ++ko)
> +        {
> +          for (eb = 0; eb < 1; ++eb)
> +            ko += pe;
> +
> +          for (ko = 0; ko < 1; ++ko)
> +            ;
> +        }
> +
> +      pe = ir = lx;
> +    }
> +}
>
--
Richard Biener <[hidden email]>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Free dominance info at the beginning of pass_jump_after_combine

Segher Boessenkool
In reply to this post by Ilya Leoshkevich
Hi!

On Tue, Nov 12, 2019 at 03:11:05PM +0100, Ilya Leoshkevich wrote:
> try_forward_edges does not update dominance info, and merge_blocks
> relies on it being up-to-date.  In PR92430 stale dominance info makes
> merge_blocks produce a loop in the dominator tree, which in turn makes
> delete_basic_block loop forever.
>
> Fix by freeing dominance info at the beginning of cleanup_cfg.

> --- a/gcc/cfgcleanup.c
> +++ b/gcc/cfgcleanup.c
> @@ -3312,6 +3312,9 @@ public:
>  unsigned int
>  pass_jump_after_combine::execute (function *)
>  {
> +  /* Jump threading does not keep dominators up-to-date.  */
> +  free_dominance_info (CDI_DOMINATORS);
> +  free_dominance_info (CDI_POST_DOMINATORS);
>    cleanup_cfg (flag_thread_jumps ? CLEANUP_THREADING : 0);
>    return 0;
>  }

Why do you always free it, if if only gets invalidated if flag_thread_jumps?

It may be a good idea to throw away the dom info anyway, but the comment
seems off then?


Segher
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Free dominance info at the beginning of pass_jump_after_combine

Ilya Leoshkevich
> Am 12.11.2019 um 15:32 schrieb Segher Boessenkool <[hidden email]>:
>
> Hi!
>
> On Tue, Nov 12, 2019 at 03:11:05PM +0100, Ilya Leoshkevich wrote:
>> try_forward_edges does not update dominance info, and merge_blocks
>> relies on it being up-to-date.  In PR92430 stale dominance info makes
>> merge_blocks produce a loop in the dominator tree, which in turn makes
>> delete_basic_block loop forever.
>>
>> Fix by freeing dominance info at the beginning of cleanup_cfg.
>
>> --- a/gcc/cfgcleanup.c
>> +++ b/gcc/cfgcleanup.c
>> @@ -3312,6 +3312,9 @@ public:
>> unsigned int
>> pass_jump_after_combine::execute (function *)
>> {
>> +  /* Jump threading does not keep dominators up-to-date.  */
>> +  free_dominance_info (CDI_DOMINATORS);
>> +  free_dominance_info (CDI_POST_DOMINATORS);
>>   cleanup_cfg (flag_thread_jumps ? CLEANUP_THREADING : 0);
>>   return 0;
>> }
>
> Why do you always free it, if if only gets invalidated if flag_thread_jumps?
>
> It may be a good idea to throw away the dom info anyway, but the comment
> seems off then?

Hmm, come to think of it, it would make sense to make flag_thread_jumps
a gate for this pass, and then run free_dominance_info (CDI_DOMINATORS)
and cleanup_cfg (CLEANUP_THREADING) unconditionally. What do you think?

Best regards,
Ilya
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Free dominance info at the beginning of pass_jump_after_combine

Segher Boessenkool
Hi!

On Tue, Nov 12, 2019 at 04:32:36PM +0100, Ilya Leoshkevich wrote:

> > Am 12.11.2019 um 15:32 schrieb Segher Boessenkool <[hidden email]>:
> > On Tue, Nov 12, 2019 at 03:11:05PM +0100, Ilya Leoshkevich wrote:
> >> unsigned int
> >> pass_jump_after_combine::execute (function *)
> >> {
> >> +  /* Jump threading does not keep dominators up-to-date.  */
> >> +  free_dominance_info (CDI_DOMINATORS);
> >> +  free_dominance_info (CDI_POST_DOMINATORS);
> >>   cleanup_cfg (flag_thread_jumps ? CLEANUP_THREADING : 0);
> >>   return 0;
> >> }
> >
> > Why do you always free it, if if only gets invalidated if flag_thread_jumps?
> >
> > It may be a good idea to throw away the dom info anyway, but the comment
> > seems off then?
>
> Hmm, come to think of it, it would make sense to make flag_thread_jumps
> a gate for this pass, and then run free_dominance_info (CDI_DOMINATORS)
> and cleanup_cfg (CLEANUP_THREADING) unconditionally. What do you think?

But we want  cleanup_cfg (0)  if the flag is not set, no?  Maybe
something like

unsigned int
pass_jump_after_combine::execute (function *)
{
  if (flag_thread_jumps)
    {
      /* Jump threading does not keep dominators up-to-date.  */
      free_dominance_info (CDI_DOMINATORS);
      cleanup_cfg (CLEANUP_THREADING);
    }
  else
    cleanup_cfg (0);

  return 0;
}

But OTOH it may well be the case that other things in cleanup_cfg make
the known dominance info invalid as well, in which case just the comment
is a bit misleading.  Sounds likely to me :-)


Segher
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Free dominance info at the beginning of pass_jump_after_combine

Ilya Leoshkevich
> On Tue, Nov 12, 2019 at 04:32:36PM +0100, Ilya Leoshkevich wrote:
>>> Am 12.11.2019 um 15:32 schrieb Segher Boessenkool <[hidden email]>:
>>> On Tue, Nov 12, 2019 at 03:11:05PM +0100, Ilya Leoshkevich wrote:
>>>> unsigned int
>>>> pass_jump_after_combine::execute (function *)
>>>> {
>>>> +  /* Jump threading does not keep dominators up-to-date.  */
>>>> +  free_dominance_info (CDI_DOMINATORS);
>>>> +  free_dominance_info (CDI_POST_DOMINATORS);
>>>>  cleanup_cfg (flag_thread_jumps ? CLEANUP_THREADING : 0);
>>>>  return 0;
>>>> }
>>>
>>> Why do you always free it, if if only gets invalidated if flag_thread_jumps?
>>>
>>> It may be a good idea to throw away the dom info anyway, but the comment
>>> seems off then?
>>
>> Hmm, come to think of it, it would make sense to make flag_thread_jumps
>> a gate for this pass, and then run free_dominance_info (CDI_DOMINATORS)
>> and cleanup_cfg (CLEANUP_THREADING) unconditionally. What do you think?
>
> But we want  cleanup_cfg (0)  if the flag is not set, no?  Maybe
> something like

When I was adding this pass, I didn't really want cleanup_cfg (0) - I
don't think this achieves anything useful at this point.  It's just that
I copied the structure of the existing code without thinking too much
about it.  But now that you brought it up...

>
> unsigned int
> pass_jump_after_combine::execute (function *)
> {
>  if (flag_thread_jumps)
>    {
>      /* Jump threading does not keep dominators up-to-date.  */
>      free_dominance_info (CDI_DOMINATORS);
>      cleanup_cfg (CLEANUP_THREADING);
>    }
>  else
>    cleanup_cfg (0);
>
>  return 0;
> }
>
> But OTOH it may well be the case that other things in cleanup_cfg make
> the known dominance info invalid as well, in which case just the comment
> is a bit misleading.  Sounds likely to me :-)

Yeah, that's what I worry about as well.  In particular, this block in
try_optimize_cfg:

       /* Try to change a conditional branch to a return to the
                 respective conditional return.  */
              if (EDGE_COUNT (b->succs) == 2
                  && any_condjump_p (BB_END (b))
                  && bb_is_just_return (BRANCH_EDGE (b)->dest, &ret, &use))
                {
                  if (redirect_jump (as_a <rtx_jump_insn *> (BB_END (b)),
                                     PATTERN (ret), 0))
                    {
                      if (use)
                        emit_insn_before (copy_insn (PATTERN (use)),
                                          BB_END (b));
                      if (dump_file)
                        fprintf (dump_file, "Changed conditional jump %d->%d "
                                 "to conditional return.\n",
                                 b->index, BRANCH_EDGE (b)->dest->index);
                      redirect_edge_succ (BRANCH_EDGE (b),
                                          EXIT_BLOCK_PTR_FOR_FN (cfun));
                      BRANCH_EDGE (b)->flags &= ~EDGE_CROSSING;
                      changed_here = true;
                    }
                }

runs regardless of cleanup mode, and it makes use of redirect_edge_succ,
which does not update dominators.

Best regards,
Ilya
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Free dominance info at the beginning of pass_jump_after_combine

Segher Boessenkool
On Wed, Nov 13, 2019 at 01:15:18PM +0100, Ilya Leoshkevich wrote:
> > But OTOH it may well be the case that other things in cleanup_cfg make
> > the known dominance info invalid as well, in which case just the comment
> > is a bit misleading.  Sounds likely to me :-)
>
> Yeah, that's what I worry about as well.  In particular, this block in
> try_optimize_cfg:

Heh, I did that code, whoops :-)

>        /* Try to change a conditional branch to a return to the
> respective conditional return.  */
>      if (EDGE_COUNT (b->succs) == 2
>  && any_condjump_p (BB_END (b))
>  && bb_is_just_return (BRANCH_EDGE (b)->dest, &ret, &use))
> {
>  if (redirect_jump (as_a <rtx_jump_insn *> (BB_END (b)),
>     PATTERN (ret), 0))
>    {
>      if (use)
> emit_insn_before (copy_insn (PATTERN (use)),
>  BB_END (b));
>      if (dump_file)
> fprintf (dump_file, "Changed conditional jump %d->%d "
> "to conditional return.\n",
> b->index, BRANCH_EDGE (b)->dest->index);
>      redirect_edge_succ (BRANCH_EDGE (b),
>  EXIT_BLOCK_PTR_FOR_FN (cfun));
>      BRANCH_EDGE (b)->flags &= ~EDGE_CROSSING;
>      changed_here = true;
>    }
> }
>
> runs regardless of cleanup mode, and it makes use of redirect_edge_succ,
> which does not update dominators.

Yeah.  Of course this only does anything if the targeted block is only
a return insn (and maybe a USE of the return value), so nothing bad will
happen, but the dom info is not technically correct anymore.


Segher