-
Notifications
You must be signed in to change notification settings - Fork 137
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Floating point exception in 2.11.1 tests #194
Comments
I don't know what would be causing this. Could you try to track down the point of failure in the code, and the values of the variables in the t-gauss_period_minpoly program (q, n, etc.) when it happens? |
Unfortunately k, g, e, n are optimised out and printf() did not work for some reason, but the other variables are there, see further below. The test passes when you compile the test without -O2, suggesting that maybe the main code is actually OK. diff --git a/arb_fmpz_poly/test/t-gauss_period_minpoly.c b/arb_fmpz_poly/test/t-gauss_period_minpoly.c
index c5e7bec..21948fb 100644
--- a/arb_fmpz_poly/test/t-gauss_period_minpoly.c
+++ b/arb_fmpz_poly/test/t-gauss_period_minpoly.c
@@ -30,6 +30,10 @@ int main()
for (q = 0; q < 1000; q++)
{
+#ifdef FLINT_TEST_DEBUG
+ flint_printf("q = %ld\n", q);
+ fflush(stdout);
+#endif
acb_dirichlet_roots_t zeta;
prec = 100 + n_randint(state, 500);
@@ -38,6 +42,10 @@ int main()
for (n = 0; n < 1000; n++)
{
+#ifdef FLINT_TEST_DEBUG
+ flint_printf("q = %ld, n = %ld\n", q, n);
+ fflush(stdout);
+#endif
arb_fmpz_poly_gauss_period_minpoly(pol, q, n);
if (!fmpz_poly_is_zero(pol))
@@ -52,6 +60,10 @@ int main()
for (iter = 0; iter < 3; iter++)
{
+#ifdef FLINT_TEST_DEBUG
+ flint_printf("q = %ld, n = %ld, iter = %ld\n", q, n, iter);
+ fflush(stdout);
+#endif
k = n_randint(state, n);
gk = n_powmod2(g, k, 2 * q);
acb_zero(u);
|
For completeness, |
If I'm reading this correctly, the the problem occurs when q = 0. In this case, arb_fmpz_poly_gauss_period_minpoly should set pol to the zero polynomial, which means the if (!fmpz_poly_is_zero(pol)) branch should not be entered. But the division by zero seems to occur inside that branch even though pol = {{coeffs = 0x0, alloc = 0, length = 0}}. I have no idea what's going on! |
The assembly is very heavily optimised and doesn't match the source code very well, things are run out-of-order. Here it is running in gdb's
Hopefully you can reproduce this yourself with |
I tried compiling the test with GCC-7; no error. |
I'm also getting this failure with This kind of smells like a compiler bug (I'm using gcc-7.2), but I will dig some more in the next few days |
Thanks. I agree that a compiler bug is plausible. It's also possible that the code contains inadvertent undefined behavior that causes problems only with the optimizations in recent GCC:s. It should be possible to produce a minimal failing example. |
The test passes with --- /usr/include/flint/longlong.h.orig 2017-10-21 01:38:05.824715526 +0200
+++ /usr/include/flint/longlong.h 2017-10-21 01:40:40.130642497 +0200
@@ -74,13 +74,35 @@
: "=a" (q), "=d" (r) \
: "0" ((mp_limb_t)(n0)), "1" ((mp_limb_t)(n1)), "rm" ((mp_limb_t)(dx)))
-/* bsrq destination must be a 64-bit register, hence mp_limb_t for __cbtmp. */
-#define count_leading_zeros(count, x) \
- do { \
- mp_limb_t __cbtmp; \
- FLINT_ASSERT ((x) != 0); \
- __asm__ ("bsrq %1,%0" : "=r" (__cbtmp) : "rm" ((mp_limb_t)(x))); \
- (count) = __cbtmp ^ (mp_limb_t) 63; \
+const unsigned char __flint_clz_tab[128] =
+{
+ 1,2,3,3,4,4,4,4,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
+ 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
+};
+#define __BITS4 (GMP_LIMB_BITS/4)
+#define count_leading_zeros(count, x) \
+ do { \
+ mp_limb_t __xr = (x); \
+ mp_limb_t __a; \
+ \
+ if (GMP_LIMB_BITS == 32) \
+ { \
+ __a = __xr < ((mp_limb_t) 1 << 2*__BITS4) \
+ ? (__xr < ((mp_limb_t) 1 << __BITS4) ? 1 : __BITS4 + 1) \
+ : (__xr < ((mp_limb_t) 1 << 3*__BITS4) ? 2*__BITS4 + 1 \
+ : 3*__BITS4 + 1); \
+ } \
+ else \
+ { \
+ for (__a = GMP_LIMB_BITS - 8; __a > 0; __a -= 8) \
+ if (((__xr >> __a) & 0xff) != 0) \
+ break; \
+ ++__a; \
+ } \
+ \
+ (count) = GMP_LIMB_BITS + 1 - __a - __flint_clz_tab[__xr >> __a]; \
} while (0)
/* bsfq destination must be a 64-bit register, "%q0" forces this in case The test inlines it via I'm not sure what this means however, whether it's a compiler bug or a flint bug. |
I'm starting to suspect it's an optimizer bug. I couldn't see anything obviously wrong with the code, though I'm not super-familiar with all the details of what is and is not undefined behaviour in C. However, I found some other seemingly-random ways to make the failure go away. diff --git a/arb_fmpz_poly/test/t-gauss_period_minpoly.c b/arb_fmpz_poly/test/t-gauss_period_minpoly.c
index c5e7bec..a626818 100644
--- a/arb_fmpz_poly/test/t-gauss_period_minpoly.c
+++ b/arb_fmpz_poly/test/t-gauss_period_minpoly.c
@@ -12,6 +12,29 @@
#include "arb_fmpz_poly.h"
#include "acb_dirichlet.h"
+#define PREINV(CONSTRAINT) \
+ mp_limb_t norm, ninv; \
+ do { mp_limb_t __cbtmp; ; __asm__ ("bsrq %1,%0" : "=r" (__cbtmp) : CONSTRAINT ((mp_limb_t)(n))); (norm) = __cbtmp ^ (mp_limb_t) 63; } while (0); \
+ do { mp_limb_t dummy; __asm__ ("divq %4" : "=a" (ninv), "=d" (dummy) : "0" ((mp_limb_t)(~((0L)))), "1" ((mp_limb_t)(~(n<<norm))), "rm" ((mp_limb_t)(n<<norm))); } while (0); \
+ return ninv
+
+static __inline__
+mp_limb_t n_preinvert_limb_bad(mp_limb_t n) { PREINV("rm"); }
+
+static __attribute__ ((noinline))
+mp_limb_t n_preinvert_limb_good1(mp_limb_t n) { PREINV("rm"); }
+
+static __inline__
+mp_limb_t n_preinvert_limb_good2(mp_limb_t n) { PREINV("m"); }
+
+#ifndef FTEST_VAR
+#define FTEST_VAR bad
+#endif
+// C sucks
+#define CONCAT_REALLY(x,y) x ## y
+#define CONCAT(x,y) CONCAT_REALLY(x,y)
+#define n_preinvert_limb_var CONCAT(n_preinvert_limb_, FTEST_VAR)
+
int main()
{
slong iter;
@@ -27,9 +50,11 @@ int main()
ulong n, q;
fmpz_poly_t pol;
fmpz_poly_init(pol);
+ mp_limb_t qx2, qx2inv;
for (q = 0; q < 1000; q++)
{
+ qx2 = 2 * q;
acb_dirichlet_roots_t zeta;
prec = 100 + n_randint(state, 500);
@@ -38,6 +63,10 @@ int main()
for (n = 0; n < 1000; n++)
{
+// these all SIGFPE
+#ifdef FTEST_OUTER
+ qx2inv = n_preinvert_limb_var(qx2);
+#endif
arb_fmpz_poly_gauss_period_minpoly(pol, q, n);
if (!fmpz_poly_is_zero(pol))
@@ -52,14 +81,18 @@ int main()
for (iter = 0; iter < 3; iter++)
{
+// these succeed when FTEST_VAR is good1 or good2
+#ifndef FTEST_OUTER
+ qx2inv = n_preinvert_limb_var(qx2);
+#endif
k = n_randint(state, n);
- gk = n_powmod2(g, k, 2 * q);
+ gk = n_powmod2_preinv(g, k, qx2, qx2inv);
acb_zero(u);
for (e = 0; e < d; e++)
{
acb_dirichlet_root(t, zeta, n_mulmod2_preinv(gk,
- n_powmod2(g, n * e, 2 * q), 2 * q, n_preinvert_limb(2 * q)), prec);
+ n_powmod2_preinv(g, n * e, qx2, qx2inv), qx2, qx2inv), prec);
acb_add(u, u, t, prec);
}
In the above, I refactor the code slightly so it only has one call to Now we copy the post-processed Because this is seemingly random, and I couldn't see any obvious UB in the file, I suspect the optimiser is to blame. However I couldn't narrow it down to one particular optimisation flag. It turns out the GCC docs are very inaccurate on which flags are enabled, but there is
i.e. However the former set of flags exhibits the sigfpe but the latter doesn't!
I also tried specifically passing the full set of I'm really stumped here, I don't know how to proceed. I was originally thinking that my diff above could lead to a minimal test case for a GCC bug report, but it turns out that seemingly random stuff is significant for the test failure so we can't remove them from the example - or at least, I can't see how to. Maybe someone else could have better luck. In the worst case, would you recommend us shipping the code (compiled with |
There is probably a less invasive way to make the test pass. Some possibilities:
Even if some workaround like this avoids the test failure, I wouldn't consider the problem solved until the cause of the bug is understood (and reported to the GCC devs if it is indeed a compiler bug) since it's likely to cause problems in other code that uses ulong_extras arithmetic. |
Right, I wasn't suggesting that you adopt the patch I added, it was just to demonstrate different test failures modes. With advice from #gcc I found a minimal optimiser setting that causes this - and a key point which unfortunately was not made explicit enough in the docs is that one cannot replace
|
Using C-reduce I managed to get a minimal example that doesn't include any flint or arb code. I'm talking to various people to see if the C/asm code has any issues, if not I'll file a bug to GCC tomorrow. |
I think flint code does have to be changed actually, but so does many other projects, so I've filed a GCC bug even though it's not (I believe) strictly their bug. |
Thanks for getting to the bottom of this. Great work! |
Thanks very much! This was a hard bug to track down, and would have taken us ages. We probably would have just worked around this, since it isn't easy to figure out at all. We really appreciate the help! |
With a fix now in flint trunk, I guess we can just add a workaround to the test code so that it passes with flint-2.5? |
I have added such a workaround. |
I tried to update flint-arb in Debian to 2.12.0 (not touching flint):
so either it's the same error message with another error, or there's still something fishy somewhere :-/ |
I think it's a different bug and a bug in the C code, I also get the same error with clang-4.0. It should probably be in a separate issue. I won't be able to look in more detail for a few days, though. |
I don't know what that is about; the valgrind output is clean for me. |
We're trying to upgrade flint-arb in Debian and running into this test failure:
I can paste more logs on request. Versions of dependencies are:
libflint-dev 2.5.2-15
libgmp-dev 2:6.1.2+dfsg-1.1
libmpfr-dev 3.1.6-1
Our config is:
The text was updated successfully, but these errors were encountered: