[Bug tree-optimization/100934] New: wrong code at -O3 on x86_64-linux-gnu

[Bug tree-optimization/100934] New: wrong code at -O3 on x86_64-linux-gnu

[zhendong.su at inf dot ethz.ch]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

            Bug ID: 100934
           Summary: wrong code at -O3 on x86_64-linux-gnu
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: zhendong.su at inf dot ethz.ch
  Target Milestone: ---

It seems to affect all versions since GCC 8.4 (but not GCC 8.3). 

[583] % gcctk -v
Using built-in specs.
COLLECT_GCC=gcctk
COLLECT_LTO_WRAPPER=/local/suz-local/software/local/gcc-trunk/libexec/gcc/x86_64-pc-linux-gnu/12.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../gcc-trunk/configure --disable-bootstrap
--prefix=/local/suz-local/software/local/gcc-trunk --enable-languages=c,c++
--disable-werror --enable-multilib --with-system-zlib
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 12.0.0 20210606 (experimental) [master revision
28c62475050:a6bc26893ec:a589877a0036fc2f66b7a957859940c53efdc7c9] (GCC) 
[584] % 
[584] % gcctk -O2 small.c; ./a.out
[585] % 
[585] % gcctk -O3 small.c
[586] % ./a.out
Segmentation fault
[587] % 
[587] % cat small.c
int a, b, c, d, e;
int main() {
  int f = 0, g = 0;
  for (; f < 2; f++) {
    int h, i;
    for (h = 0; h < 2; h++) {
      b = e = g ? a % g : 0;
      c = d;
      for (i = 0; i < 1; i++)
        g = 0;
      for (; g < 2; g++)
        ;
    }
  }
  return 0;
}

[Bug tree-optimization/100934] [9/10/11/12 Regression] wrong code at -O3 during unrolling

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |x86_64-linux-gnu
             Status|UNCONFIRMED                 |NEW
            Summary|wrong code at -O3 on        |[9/10/11/12 Regression]
                   |x86_64-linux-gnu            |wrong code at -O3 during
                   |                            |unrolling
           Keywords|                            |wrong-code
   Last reconfirmed|                            |2021-06-06
      Known to fail|                            |12.0
     Ever confirmed|0                           |1

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The complete unroller is adding a __builtin_unreachable and then that becomes
the only thing.

[Bug tree-optimization/100934] [9/10/11/12 Regression] wrong code at -O3 during unrolling since r9-6299

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|unknown                     |12.0
   Target Milestone|---                         |9.5
                 CC|                            |jakub at gcc dot gnu.org
            Summary|[9/10/11/12 Regression]     |[9/10/11/12 Regression]
                   |wrong code at -O3 during    |wrong code at -O3 during
                   |unrolling                   |unrolling since r9-6299

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r9-6299-gd7a700e0a701e5164b8c547f76a2d91f657eee97

[Bug tree-optimization/100934] [9/10/11/12 Regression] wrong code at -O3 during unrolling since r9-6299

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mpolacek at gcc dot gnu.org

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
And that has been backported in
r8-9182-gfbbfed2085940bbd2822d7ae55d96e8351127c35
to 8.x which would explain the 8.5 thing.

[Bug tree-optimization/100934] [9/10/11/12 Regression] wrong code at -O3 during unrolling since r9-6299

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
      Known to fail|                            |8.5.0

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will have a look.

[Bug tree-optimization/100934] [9/10/11/12 Regression] wrong code at -O3 during unrolling since r9-6299

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at gcc dot gnu.org

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Somehow niter analysis computes two iterations for the loop but that doesn't
look correct.  That might be the result of extra simplification triggered by
the change but it most definitely looks like a latent issue to me

  <bb 2> [local count: 119883187]:
  d.3_2 = d;
  a.1_1 = a;
  iftmp.0_17 = a.1_1 % 2;
  goto <bb 4>; [100.00%]

  <bb 12> [local count: 0]:

  <bb 3> [local count: 59073784]:
  # h_29 = PHI <0(7), h_21(12)>
  # f_26 = PHI <_30(7), f_31(12)>

  <bb 4> [local count: 239802342]:
  # iftmp.0_10 = PHI <iftmp.0_17(3), 0(2)>
  # h_28 = PHI <h_29(3), 0(2)>
  # f_31 = PHI <f_26(3), 0(2)>
  h_21 = h_28 + 1;
  _30 = f_31 + 1;
  if (h_21 != 2)
    goto <bb 12>; [0.00%]
  else
    goto <bb 7>; [100.00%]

  <bb 7> [local count: 239802342]:
  if (_30 != 2)
    goto <bb 3>; [50.01%]
  else
    goto <bb 8>; [49.99%]

  <bb 8> [local count: 119883187]:
  # iftmp.0_20 = PHI <iftmp.0_10(7)>
  c = d.3_2;
  b = iftmp.0_20;
  e = iftmp.0_20;
  return 0;

}

niter is chrec_don't_know but we have a set nb_iterations_upper_bound which
likely survives incorrectly from some CFG merging.  In fact loops are
removed at

a-t.c.109t.thread1:fix_loop_structure: removing loop 3
a-t.c.123t.thread2:fix_loop_structure: removing loop 2
a-t.c.152t.cddce2:fix_loop_structure: removing loop 4

loop 1 gets its nb_iterations_upper_bound in EVRP but when loop 2 is
removed it is not reset appropriately. In fact thread2 creates quite some
mess which includes turning loop2 into some irreducible region.

There's some scattered resetting of the upper bound (estimates) but no
API for this (and free_numbers_of_iterations_estimates doesn't do it).

              loop_father->any_upper_bound = false;
              loop_father->any_likely_upper_bound = false;

in fact we only have

gimple-loop-interchange.cc:  iloop.m_loop->any_upper_bound = false;
gimple-loop-interchange.cc:  oloop.m_loop->any_upper_bound = false;
tree-cfgcleanup.c:            dest->loop_father->any_upper_bound = false;
tree-vectorizer.c:  loop->any_upper_bound = false;

I think the backwards threader has to get some guards - whenever we thread
through a loop latch edge we have to reset niter estimates/bounds.  But I'm
not at all familiar with said code.  Jeff - do you know a single place to
tackle this?

[Bug tree-optimization/100934] [9/10/11/12 Regression] wrong code at -O3 during unrolling since r9-6299

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|rguenth at gcc dot gnu.org         |unassigned at gcc dot gnu.org
           Priority|P3                          |P2
                 CC|                            |rguenth at gcc dot gnu.org
             Status|ASSIGNED                    |NEW

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Not working on this at the moment.

[Bug tree-optimization/100934] [9/10/11/12 Regression] wrong code at -O3 during unrolling since r9-6299

[law at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

--- Comment #7 from Jeffrey A. Law <law at gcc dot gnu.org> ---
So when we're finding jump threads we know if we thread through the loop latch
and we note when that's going to create an irreducible region.   We generally
suppress threading through the latch before the loop optimizers have run, but
allow it afterwards.

But I'm not aware of a really good place to adjust the loop bound estimates,
particularly for the backwards threader.  THe backwards threader uses copy_bbs
API, so much of the guts of what's happening is opaque.

Peek at jump_thread_path_registry:::duplicate_thread_path.  All the backwards
threader bits go through there at some point.

[Bug tree-optimization/100934] [9/10/11/12 Regression] wrong code at -O3 during unrolling since r9-6299

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #7)
> So when we're finding jump threads we know if we thread through the loop
> latch and we note when that's going to create an irreducible region.   We
> generally suppress threading through the latch before the loop optimizers
> have run, but allow it afterwards.
> 
> But I'm not aware of a really good place to adjust the loop bound estimates,
> particularly for the backwards threader.  THe backwards threader uses
> copy_bbs API, so much of the guts of what's happening is opaque.
> 
> Peek at jump_thread_path_registry:::duplicate_thread_path.  All the
> backwards threader bits go through there at some point.

OK, so it looks like mark_threaded_blocks already has code to deal with this:

                  if (crossed_headers > 1)
                    {
                      vect_free_loop_info_assumptions
                        ((*path)[path->length () - 1]->e->dest->loop_father);
                      break;

but mark_threaded_blocks is only called after we process all FSM paths though
it's handling of the case wouldn't necessarily fix this instance where we
just duplicate the loop header incoming its backedge and to one of its
destination still in the same loop.

It looks like applying the FSM threads goes through different code paths
than the regular threading...

But the issue at hand must be more subtle since invalidating the number of
iterations on the loop that is then removed of course doesn't change
anything.  Still it is likely going to be an issue.  Possible fix for that
but not this testcase:

diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index a86302be18e..4e31fa8f5c2 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -2379,12 +2379,15 @@ jump_thread_path_registry::duplicate_thread_path (edge
entry,
      missuses of the functions.  I.e. if you ask to copy something weird,
      it will work, but the state of structures probably will not be
      correct.  */
+  bool loop_header_duplicated = false;
   for (i = 0; i < n_region; i++)
     {
       /* We do not handle subloops, i.e. all the blocks must belong to the
         same loop.  */
       if (region[i]->loop_father != loop)
        return false;
+      if (region[i]->loop_father == loop)
+       loop_header_duplicated = true;
     }

   initialize_original_copy_tables ();
@@ -2501,6 +2504,11 @@ jump_thread_path_registry::duplicate_thread_path (edge
entry,
   /* Add the other PHI node arguments.  */
   add_phi_args_after_copy (region_copy, n_region, NULL);

+  /* Invalidate loop niter information if the loop header was part of the
+     thread path.  */
+  if (loop_header_duplicated)
+    vect_free_loop_info_assumptions (loop);
+
   free (region_copy);

   adjust_paths_after_duplication (current_path_no);


The actual issue seems to be that the DOM pass following the problematic
threading threads additional paths through loop headers which ends up
rotating the loop and also affecting niter estimates since it crosses
a irreducible region boundary.  Ah - but we have _not_ marked irreducible
regions but we are querying them from DOM threading!

diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 075b1ccb9de..c231e6c8467 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -727,7 +727,8 @@ pass_dominator::execute (function *fun)
      gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
      missing.  We should improve jump threading in future then
      LOOPS_HAVE_PREHEADERS won't be needed here.  */
-  loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
+  loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES
+                      | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);

   /* We need accurate information regarding back edges in the CFG
      for jump threading; this may include back edges that are not part of

fixes the testcase.

[Bug tree-optimization/100934] [9/10/11/12 Regression] wrong code at -O3 during unrolling since r9-6299

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #8)
> --- a/gcc/tree-ssa-threadupdate.c
> +++ b/gcc/tree-ssa-threadupdate.c
> @@ -2379,12 +2379,15 @@ jump_thread_path_registry::duplicate_thread_path
> (edge entry,
>       missuses of the functions.  I.e. if you ask to copy something weird,
>       it will work, but the state of structures probably will not be
>       correct.  */
> +  bool loop_header_duplicated = false;
>    for (i = 0; i < n_region; i++)
>      {
>        /* We do not handle subloops, i.e. all the blocks must belong to the
>          same loop.  */
>        if (region[i]->loop_father != loop)
>         return false;
> +      if (region[i]->loop_father == loop)
> +       loop_header_duplicated = true;

The if right above this returns false if loop_father is not loop, so
wouldn't be loop_header_duplicated == true whenever n_region != 0 (or always)?

[Bug tree-optimization/100934] [9/10/11/12 Regression] wrong code at -O3 during unrolling since r9-6299

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

--- Comment #10 from rguenther at suse dot de <rguenther at suse dot de> ---
On Mon, 14 Jun 2021, jakub at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934
> 
> --- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
> (In reply to Richard Biener from comment #8)
> > --- a/gcc/tree-ssa-threadupdate.c
> > +++ b/gcc/tree-ssa-threadupdate.c
> > @@ -2379,12 +2379,15 @@ jump_thread_path_registry::duplicate_thread_path
> > (edge entry,
> >       missuses of the functions.  I.e. if you ask to copy something weird,
> >       it will work, but the state of structures probably will not be
> >       correct.  */
> > +  bool loop_header_duplicated = false;
> >    for (i = 0; i < n_region; i++)
> >      {
> >        /* We do not handle subloops, i.e. all the blocks must belong to the
> >          same loop.  */
> >        if (region[i]->loop_father != loop)
> >         return false;
> > +      if (region[i]->loop_father == loop)
> > +       loop_header_duplicated = true;
> 
> The if right above this returns false if loop_father is not loop, so
> wouldn't be loop_header_duplicated == true whenever n_region != 0 (or always)?

whoops yes, this should be region[i] == loop->header but as said the
issue is elsewhere (patch in testing) and the issue in 
duplicate_thread_path does not have a testcase yet.

[Bug tree-optimization/100934] [9/10/11/12 Regression] wrong code at -O3 during unrolling since r9-6299

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

--- Comment #11 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:788bb7edb3975b80c4cb16323e7a5e55a2471e46

commit r12-1432-g788bb7edb3975b80c4cb16323e7a5e55a2471e46
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Jun 14 14:57:26 2021 +0200

    tree-optimization/100934 - properly mark irreducible regions for DOM

    The jump threading code requires marked irreducible regions for the
    purpose of validating jump threading paths but DOM fails to provide
    that resulting in mised number of iteration upper bounds clearing.

    2021-06-14  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/100934
            * tree-ssa-dom.c (pass_dominator::execute): Properly
            mark irreducible regions.

            * gcc.dg/torture/pr100934.c: New testcase.

[Bug tree-optimization/100934] [9/10/11 Regression] wrong code at -O3 during unrolling since r9-6299

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|12.0                        |11.1.0
            Summary|[9/10/11/12 Regression]     |[9/10/11 Regression] wrong
                   |wrong code at -O3 during    |code at -O3 during
                   |unrolling since r9-6299     |unrolling since r9-6299
      Known to work|                            |12.0

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk sofar.

[Bug tree-optimization/100934] [9/10/11 Regression] wrong code at -O3 during unrolling since r9-6299

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

--- Comment #13 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:8c90437109c30a0b6d2cf861c6f0cee8b69965ef

commit r11-8579-g8c90437109c30a0b6d2cf861c6f0cee8b69965ef
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Jun 14 14:57:26 2021 +0200

    tree-optimization/100934 - properly mark irreducible regions for DOM

    The jump threading code requires marked irreducible regions for the
    purpose of validating jump threading paths but DOM fails to provide
    that resulting in mised number of iteration upper bounds clearing.

    2021-06-14  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/100934
            * tree-ssa-dom.c (pass_dominator::execute): Properly
            mark irreducible regions.

            * gcc.dg/torture/pr100934.c: New testcase.

    (cherry picked from commit 788bb7edb3975b80c4cb16323e7a5e55a2471e46)

[Bug tree-optimization/100934] [9/10 Regression] wrong code at -O3 during unrolling since r9-6299

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

--- Comment #14 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:b7878d4e179c72ad69cdd103fbbfe16bc38010db

commit r10-9924-gb7878d4e179c72ad69cdd103fbbfe16bc38010db
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Jun 14 14:57:26 2021 +0200

    tree-optimization/100934 - properly mark irreducible regions for DOM

    The jump threading code requires marked irreducible regions for the
    purpose of validating jump threading paths but DOM fails to provide
    that resulting in mised number of iteration upper bounds clearing.

    2021-06-14  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/100934
            * tree-ssa-dom.c (pass_dominator::execute): Properly
            mark irreducible regions.

            * gcc.dg/torture/pr100934.c: New testcase.

    (cherry picked from commit 788bb7edb3975b80c4cb16323e7a5e55a2471e46)

[Bug tree-optimization/100934] [9 Regression] wrong code at -O3 during unrolling since r9-6299

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

--- Comment #15 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-9 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:e89b09601907f3f3ba6c988ebef7b978af40b83a

commit r9-9769-ge89b09601907f3f3ba6c988ebef7b978af40b83a
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Jun 14 14:57:26 2021 +0200

    tree-optimization/100934 - properly mark irreducible regions for DOM

    The jump threading code requires marked irreducible regions for the
    purpose of validating jump threading paths but DOM fails to provide
    that resulting in mised number of iteration upper bounds clearing.

    2021-06-14  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/100934
            * tree-ssa-dom.c (pass_dominator::execute): Properly
            mark irreducible regions.

            * gcc.dg/torture/pr100934.c: New testcase.

    (cherry picked from commit 788bb7edb3975b80c4cb16323e7a5e55a2471e46)

[Bug tree-optimization/100934] [9 Regression] wrong code at -O3 during unrolling since r9-6299

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED
      Known to fail|                            |9.4.0

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.

[Bug tree-optimization/100934] [9 Regression] wrong code at -O3 during unrolling since r9-6299

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100934

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |qrzhang at gatech dot edu

--- Comment #17 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 101001 has been marked as a duplicate of this bug. ***