[Bug middle-end/108687] New: Non-termination since gcc-13-5630-g881bf8de9b0

[Bug middle-end/108687] New: Non-termination since gcc-13-5630-g881bf8de9b0

[stefansf at linux dot ibm.com]

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

            Bug ID: 108687
           Summary: Non-termination since gcc-13-5630-g881bf8de9b0
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: stefansf at linux dot ibm.com
  Target Milestone: ---

typedef struct { int a[32]; } b;
b c;
int d, e, f;
void g () {
  for (; c.a[f - 1]; f++) {
    e = e * d;
    c.a[f] = f / d;
  }
}

Running gcc -O3 -c t.c on s390x does not terminate. Started with
gcc-13-5630-g881bf8de9b0

[Bug middle-end/108687] Non-termination since r13-5630-g881bf8de9b0

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Non-termination since       |Non-termination since
                   |gcc-13-5630-g881bf8de9b0    |r13-5630-g881bf8de9b0

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
r13-5630-g881bf8de9b0

[Bug middle-end/108687] Non-termination since r13-5630-g881bf8de9b0

[stefansf at linux dot ibm.com]

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

--- Comment #2 from Stefan Schulze Frielinghaus <stefansf at linux dot ibm.com> ---
(In reply to Stefan Schulze Frielinghaus from comment #0)
> Running gcc -O3 -c t.c on s390x does not terminate.

More specifically: gcc -O3 -march=z13 -c t.c

[Bug middle-end/108687] Non-termination since r13-5630-g881bf8de9b0

[stefansf at linux dot ibm.com]

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

--- Comment #3 from Stefan Schulze Frielinghaus <stefansf at linux dot ibm.com> ---
Created attachment 54415
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54415&action=edit
Random backtrace after some time

[Bug middle-end/108687] Non-termination since r13-5630-g881bf8de9b0

[stefansf at linux dot ibm.com]

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

--- Comment #4 from Stefan Schulze Frielinghaus <stefansf at linux dot ibm.com> ---
I have added a backtrace from GDB where I randomly interrupted. Hope this helps
to narrow it down.

[Bug middle-end/108687] [13 Regression] Non-termination since r13-5630-g881bf8de9b0

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Non-termination since       |[13 Regression]
                   |r13-5630-g881bf8de9b0       |Non-termination since
                   |                            |r13-5630-g881bf8de9b0
           Keywords|                            |compile-time-hog
   Target Milestone|---                         |13.0

[Bug tree-optimization/108687] [13 Regression] Non-termination since r13-5630-g881bf8de9b0

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |jakub at gcc dot gnu.org

[Bug tree-optimization/108687] [13 Regression] Non-termination since r13-5630-g881bf8de9b0

[amacleod at redhat dot com]

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

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---
My cross compiler doesn't seem to exhibit this behaviour. It simply compiles
this as a quite short program.

It looks like it in the DOM pass.. could you try it with:


-fdump-tree-all-detail --param=ranger-debug=all

stop it very shortly after it runs, if it is in a loop of some sort, one of
these output files is going to grow very quickly.. probably one of:

t.c*dom2 or
t.c*dom3

I might be able to tell from the debug output where the cycle is.  Doesnt need
to be attached here, you could just email it to me.

Or is there some other way to reproduce this?  I don't have access to a s390 at
the moment. Any chance the compiler is miscompiled?   does the same thing
happen with a stage 1 compiler?

[Bug tree-optimization/108687] [13 Regression] Non-termination since r13-5630-g881bf8de9b0

[stefansf at linux dot ibm.com]

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

--- Comment #6 from Stefan Schulze Frielinghaus <stefansf at linux dot ibm.com> ---
Just to be sure: in the initial commit I missed adding -march=z13 and only
mentioned it in commit 2

I will come up with those logs and mail them to you.

[Bug tree-optimization/108687] [13 Regression] Non-termination since r13-5630-g881bf8de9b0

[amacleod at redhat dot com]

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

--- Comment #7 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Stefan Schulze Frielinghaus from comment #6)
> Just to be sure: in the initial commit I missed adding -march=z13 and only
> mentioned it in commit 2
> 
> I will come up with those logs and mail them to you.

yeah, I was compiling with -march=z13 too.

[Bug tree-optimization/108687] [13 Regression] Non-termination since r13-5630-g881bf8de9b0

[stefansf at linux dot ibm.com]

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

--- Comment #8 from Stefan Schulze Frielinghaus <stefansf at linux dot ibm.com> ---
I came up with a cross compiler where I can reproduce it:

FROM fedora:37
RUN dnf -y upgrade \
  && dnf -y install 'dnf-command(builddep)' \
  && dnf -y builddep gcc \
  && dnf -y install binutils-s390x-linux-gnu git \
  && dnf clean metadata
RUN git clone --depth 1 https://gcc.gnu.org/git/gcc.git \
  && mkdir /build \
  && cd /build \
  && /gcc/configure --target=s390x-linux-gnu \
                    --enable-languages=c \
                    --disable-nls \
                    --without-headers \
                    --disable-multilib \
  && make -j$(nproc) all-gcc \
  && make install-gcc

Running inside the container

$ /usr/local/bin/s390x-linux-gnu-gcc -O3 -march=z13 -c t.c

does not terminate for me. Hope this makes debugging easier. If you need
anything else just let me know.

[Bug tree-optimization/108687] [13 Regression] Non-termination since r13-5630-g881bf8de9b0

[amacleod at redhat dot com]

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

--- Comment #9 from Andrew Macleod <amacleod at redhat dot com> ---
Created attachment 54445
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54445&action=edit
proposed patch

I finally reproduced it, the following patch is in testing.

In the referenced commit, I changed it so cache propagation would use better
values from the DOM tree if there was nothing in the current block.  I changed
the external cache API to do this rather than reverting to using the internal
API.

The result was when GORI is calculating outgoing ranges, if it finds a
recomputation candidate, it invokes the caches range_on_edge API to resolve the
operands of the recompution.

With my earlier change, this could do a search of the DOM tree for a better
value. With the proer set of cascading expressions feeding each other this
could be a quadratic cost, approaching exponential.   Doh.

The correct fix is to revert the range_on_edge external API to return to its
original approach of just using whats handy, and instead change range_from_dom
to use the internal API since it knows what its doing, and check the dom tree
for a better value.

This could in theory be the cause of other time hogs recently, especially in
DOM.

[Bug tree-optimization/108687] [13 Regression] Non-termination since r13-5630-g881bf8de9b0

[stefansf at linux dot ibm.com]

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

--- Comment #10 from Stefan Schulze Frielinghaus <stefansf at linux dot ibm.com> ---
Can confirm the attached patch solves this issue.

[Bug tree-optimization/108687] [13 Regression] Non-termination since r13-5630-g881bf8de9b0

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:6493b7af37e473a89c67afab474330f931dd8447

commit r13-5807-g6493b7af37e473a89c67afab474330f931dd8447
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Thu Feb 9 17:50:07 2023 -0500

    Query rangers cache in readonly mode only from within

    The change for 108356 allowed the cache to scan the dominator trees when
    it was attempting a lookup rather than using the local value.  I
    inadvertantly changed the externbal interface to also do this, so all
    the GORI queries via range_on_edge of the cache could also do lookups.

    This triggered a quadratic, possible expoential time increase when
    the right conditions were presented. That being a cascading series of
    recomputaions on outgoing edge calucaltions that at then searched the dom
tree
    instead of being a simple calcualtion using whats easily available.

    The fix is to use the internal API within the cache rather than the
    extrenal one that GORI uses.   This leaves GORI computations to be
    resovled in linear time.

            PR tree-optimization/108687
            gcc/
            * gimple-range-cache.cc (ranger_cache::range_on_edge): Revert
            back to RFD_NONE mode for calculations.
            (ranger_cache::propagate_cache): Call the internal edge range API
            with RFD_READ_ONLY instead of changing the external routine.

[Bug tree-optimization/108687] [13 Regression] Non-termination since r13-5630-g881bf8de9b0

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|UNCONFIRMED                 |RESOLVED

--- Comment #12 from Andrew Macleod <amacleod at redhat dot com> ---
should be fixed.