[Bug middle-end/96044] New: GCC hangs in tight loop resolving __builtin_jn using MPFR

[Bug middle-end/96044] New: GCC hangs in tight loop resolving __builtin_jn using MPFR

[acoplan at gcc dot gnu.org]

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

            Bug ID: 96044
           Summary: GCC hangs in tight loop resolving __builtin_jn using
                    MPFR
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: acoplan at gcc dot gnu.org
  Target Milestone: ---

On the following code:

void f(void)
{
  __builtin_jn(73333,73333);
}

GCC since 4.3 hangs in a tight loop inside MPFR code trying to constant fold
the call away.

[Bug middle-end/96044] GCC hangs in tight loop resolving __builtin_jn using MPFR

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2020-07-03
                 CC|                            |vincent-gcc at vinc17 dot net

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
It works for me (but takes ~16 seconds to constant fold on a fast machine). 
This is with mpfr 4.0.1 and gmp 6.1.2.

Can you share more info?

[Bug middle-end/96044] GCC hangs in tight loop resolving __builtin_jn using MPFR

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Could this be a bug in MPFR?

      return do_mpfr_arg2 (result, mpfr_jn, arg0, arg1, format);

do_mpfr_arg2 does:
  mpfr_inits2 (prec, m0, m1, NULL);
  mpfr_from_real (m0, arg0, MPFR_RNDN);
  mpfr_from_real (m1, arg1, MPFR_RNDN);
  mpfr_clear_flags ();
  bool inexact = func (m0, m0, m1, rnd);
  bool ok = do_mpfr_ckconv (result, m0, inexact, format);
  mpfr_clears (m0, m1, NULL);


That is a bug in mpfr_jn ?

[Bug middle-end/96044] GCC hangs in tight loop resolving __builtin_jn using MPFR

[acoplan at gcc dot gnu.org]

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

--- Comment #3 from Alex Coplan <acoplan at gcc dot gnu.org> ---
Ah, it appears I just wasn't being patient enough. It seems you can make the
constant folding take longer (arbitrarily long?) by adding another digit to the
arguments.

This code:

void f(void) {
  __builtin_jn(733333,733333);
}

has been compiling for >= 1 minute for me.

[Bug middle-end/96044] GCC hangs in tight loop resolving __builtin_jn using MPFR

[acoplan at gcc dot gnu.org]

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

--- Comment #4 from Alex Coplan <acoplan at gcc dot gnu.org> ---
I left the updated version running for ~1 hour and it didn't finish compiling.

[Bug middle-end/96044] GCC hangs in tight loop resolving __builtin_jn using MPFR

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |NEW

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
I can confirm that with the updated testcase and my versions of mpfr/gmp it
takes longer than I'm willing to wait.  Possibly evaluating bessel functions
cannot be done faster though which means the reasonable way to handle them
would be not
constant folding any of them?

Vincent, any guidance on that?  I guess the actual runtime implementation in
glibc may be "fast" because it's not accurate (evaluating takes 0.00s with
glibc 2.26 ...)

[Bug middle-end/96044] GCC hangs in tight loop resolving __builtin_jn using MPFR

[vincent-gcc at vinc17 dot net]

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

--- Comment #6 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
(In reply to Richard Biener from comment #5)
> Vincent, any guidance on that?  I guess the actual runtime implementation in
> glibc may be "fast" because it's not accurate (evaluating takes 0.00s with
> glibc 2.26 ...)

I confirm the issue. I've just added this testcase in MPFR.

[Bug middle-end/96044] GCC hangs in tight loop resolving __builtin_jn using MPFR

[zimmerma+gcc at loria dot fr]

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

Paul Zimmermann <zimmerma+gcc at loria dot fr> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |zimmerma+gcc at loria dot fr

--- Comment #7 from Paul Zimmermann <zimmerma+gcc at loria dot fr> ---
the problem is partly solved in MPFR development branch, where jn(73333,73333)
now takes about 2 seconds on my machine, and jn(733333,733333) about 4 minutes.
Note that Wolfram Alpha fails for jn(73333,73333), and Pari/GP fails for
jn(733333,733333). Maybe a timeout should be put into the constant folding
code?

With MPFR I get 4.9602731659759520e-03 whereas gcc -fno-builtin gives
4.9602731659753978e-03, which is off by 639 ulps (assuming the MPFR value is
correct).

[Bug middle-end/96044] GCC hangs in tight loop resolving __builtin_jn using MPFR

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Paul Zimmermann from comment #7)
> the problem is partly solved in MPFR development branch, where
> jn(73333,73333) now takes about 2 seconds on my machine, and
> jn(733333,733333) about 4 minutes.
> Note that Wolfram Alpha fails for jn(73333,73333), and Pari/GP fails for
> jn(733333,733333). Maybe a timeout should be put into the constant folding
> code?

The issue with timeouts (as in wall-clock) is that it makes builds
dependent on CPU speed which is something we generally avoid.  For ISL
computations where we employ this kind of thing there's tracking of
"number of ops" that are performed by ISL itself plus the ability for
the client to set an upper bound after which operations return with
an appropriate error.  gmp/mpfr/mpc could for example track the number
of 64bit multiplies and support limiting there - but I expect this would
be a lot of work.  Eventually we could make GCC use mini-gmp (would
a host libmpfr then use the built-in mini-gmp?) and patch in this kind
of accounting there...

But IMHO simply classifying a value-range where we do and where we do not
constant fold certain functions would be reasonable as well - unless C++
at some point magically requires to constexpr evaluate jn().

> With MPFR I get 4.9602731659759520e-03 whereas gcc -fno-builtin gives
> 4.9602731659753978e-03, which is off by 639 ulps (assuming the MPFR value is
> correct).

[Bug middle-end/96044] GCC hangs in tight loop resolving __builtin_jn using MPFR

[zimmerma+gcc at loria dot fr]

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

--- Comment #9 from Paul Zimmermann <zimmerma+gcc at loria dot fr> ---
Dear Richard, about mini-gmp, note that MPFR 4.1.0 (rc2 now in test) will come
with improved mini-gmp support. From NEWS:

- Mini-gmp support: replaced --enable-mini-gmp configure option by
--with-mini-gmp (still experimental, read doc/mini-gmp).

Feel free to exercise this within GCC.

[Bug middle-end/96044] GCC hangs in tight loop resolving __builtin_jn using MPFR

[vincent-gcc at vinc17 dot net]

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

--- Comment #10 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
(In reply to Richard Biener from comment #8)
> The issue with timeouts (as in wall-clock) is that it makes builds
> dependent on CPU speed which is something we generally avoid.  For ISL
> computations where we employ this kind of thing there's tracking of
> "number of ops" that are performed by ISL itself plus the ability for
> the client to set an upper bound after which operations return with
> an appropriate error.  gmp/mpfr/mpc could for example track the number
> of 64bit multiplies and support limiting there - but I expect this would
> be a lot of work.  Eventually we could make GCC use mini-gmp (would
> a host libmpfr then use the built-in mini-gmp?) and patch in this kind
> of accounting there...

The result would depend on the algorithm, i.e. on the MPFR version. And for
this reason, I agree with:

> But IMHO simply classifying a value-range where we do and where we do not
> constant fold certain functions would be reasonable as well - unless C++
> at some point magically requires to constexpr evaluate jn().