NetBSD Problem Report #47301

From www@NetBSD.org  Sun Dec  9 15:57:24 2012
Return-Path: <www@NetBSD.org>
Received: from mail.netbsd.org (mail.netbsd.org [149.20.53.66])
	by www.NetBSD.org (Postfix) with ESMTP id E3FD663EA85
	for <gnats-bugs@gnats.NetBSD.org>; Sun,  9 Dec 2012 15:57:23 +0000 (UTC)
Message-Id: <20121209155722.576EA63EA85@www.NetBSD.org>
Date: Sun,  9 Dec 2012 15:57:22 +0000 (UTC)
From: tg@gmplib.org.dontsendmailthere
Reply-To: tg@gmplib.org.dontsendmailthere
To: gnats-bugs@NetBSD.org
Subject: Miscompilation by bundled GCC
X-Send-Pr-Version: www-1.0

>Number:         47301
>Category:       bin
>Synopsis:       Miscompilation by bundled GCC
>Confidential:   no
>Severity:       serious
>Priority:       low
>Responsible:    toolchain-manager
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Sun Dec 09 16:00:01 +0000 2012
>Last-Modified:  Tue Nov 08 19:25:00 +0000 2016
>Originator:     Torbjorn Granlund
>Release:        NetBSD 6.0
>Organization:
KTH, Sweden
>Environment:
NetBSD slug.gmplib.org 6.0 NetBSD 6.0 (GENERIC) vax
>Description:
The current GMP source code is miscompiled by /usr/bin/gcc.
The result is crashes in n-factorial computations.
>How-To-Repeat:
Either get ftp://gmplib.org/pub/snapshot/gmp-5.1.0-RC1.tar.xz
and isolate the problem of oddfac_1.c in mpz_oddfac_1.  Expect a crash
for n <= ODD_FACTORIAL_TABLE_LIMIT.

I have created a smaller test case which I have not executed, but
where it is very obvious that there is a miscompile.

Source:

typedef unsigned long int mp_limb_t;
typedef struct
{
int _mp_alloc;
int _mp_size;
mp_limb_t *_mp_d;
} __mpz_struct;
typedef __mpz_struct mpz_t[1];
typedef mp_limb_t * mp_ptr;
typedef long int mp_size_t;
typedef __mpz_struct *mpz_ptr;
extern const mp_limb_t __gmp_oddfac_table[];
extern const mp_limb_t __gmp_odd2fac_table[];
static mp_limb_t id_to_n (mp_limb_t id) { return id*3+1+(id&1); }
static mp_limb_t n_to_bit (mp_limb_t n) { return ((n-5)|1)/3U; }
static mp_limb_t limb_apprsqrt (mp_limb_t x) { return x; }
static void
mpz_2multiswing_1 (mpz_ptr x, mp_limb_t n, mp_ptr sieve, mp_ptr factors)
{
  mp_limb_t prod, max_prod;
  mp_size_t j;
  j = 0;
  prod = -(n & 1);
  n &= ~1L;
  prod = (prod & n) + 1;
  max_prod = ((~ ((mp_limb_t) (0))) >> 0) / (n-1);
  mp_limb_t __q, __prime;
  __prime = 3;
  if (prod > max_prod)
    {
      factors[j++] = prod;
      prod = 1;
    }
  __q = n;
  do {
    __q /= __prime;
    if ((__q & 1) != 0)
      prod *= __prime;
  } while (__q >= __prime);

  mp_limb_t s;
  mp_limb_t prime;
  s = limb_apprsqrt(n);
  s = n_to_bit (s);
  mp_limb_t __mask, __index, __max_i, __i;
  __i = n_to_bit (5);
  __index = __i / 32;
  __mask = ((mp_limb_t) 1L) << (__i % 32);
  __i += 0;
  __max_i = s;
  do {
    ++__i;
    if ((sieve[__index] & __mask) == 0)
      {
        prime = id_to_n(__i);
        mp_limb_t __q, __prime;
        __prime = prime;
        if (prod > max_prod)
          {
            factors[j++] = prod;
            prod = 1;
          }
        __q = n;
        do {
            __q /= __prime;
            if ((__q & 1) != 0)
              prod *= __prime;
        } while (__q >= __prime);
      }
    __mask = __mask << 1 | __mask >> 31;
    __index += __mask & 1;
  } while (__i <= __max_i);
  s++;

  if (j != 0)
    {
      factors[j++] = prod;
      __gmpz_prodlimbs (x, factors, j);
    }
}
void
miscompiled_function (mpz_ptr x, mp_limb_t n, unsigned flag)
{
  if (n <= 16)
    {
      /* This is miscompiled.  The store address is completely bogus.  */
      mp_limb_t xxx = __gmp_oddfac_table[n];
      (x->_mp_d)[0] = xxx;
      (x->_mp_size) = 1;
    }
  else
    {
      unsigned s;
      mp_ptr factors;
      mp_limb_t tn;
      mp_limb_t prod, max_prod, i;
      mp_size_t j;
      s = 0;
      for (tn = n; tn >= 400; s++)
        tn >>= 1;
      j = 0;
      factors = (mp_limb_t *) __builtin_alloca(199 * sizeof (mp_limb_t));
      prod = 1;
      max_prod = 98723491;
      do {
        i = 21;
        factors[j++] = 0x27065f73L;
        do {
          if (prod > max_prod)
            {
              factors[j++] = prod;
              prod = i;
            }
          else
            prod *= i;
          i += 2;
        } while (i <= tn);
        max_prod <<= 1;
        tn >>= 1;
      } while (tn > 20);
      factors[j++] = prod;
      factors[j++] = __gmp_odd2fac_table[(tn - 1) >> 1];
      factors[j++] = __gmp_oddfac_table[tn >> 1];
      __gmpz_prodlimbs (x, factors, j);

      if (s != 0)
        {
          mpz_t mswing;
          mp_ptr sieve;
          mp_size_t size;
          size = n / (32 - 0) + 4;
          mpz_ptr __x = mswing;
          __x->_mp_alloc = size;
          __x->_mp_d = (mp_limb_t *) __builtin_alloca(size * sizeof (mp_limb_t));
          sieve = (mswing->_mp_d) + size / 2 + 1;
          size = (__gmp_primesieve (sieve, n - 1) + 1) / n + 1;
          factors = (mp_limb_t *) __builtin_alloca(size * sizeof (mp_limb_t));
          do
            {
              mp_ptr square, px;
              mp_size_t nx, ns;
              mp_limb_t cy;
              s--;
              mpz_2multiswing_1 (mswing, n >> s, sieve, factors);
              nx = (x->_mp_size);
              ns = (mswing->_mp_size);
              nx = size + ns;
              px = (nx) > (x->_mp_alloc) != 0 ? (mp_ptr) __gmpz_realloc(x,nx) : x->_mp_d;
              cy = __gmpn_mul (px, square, size, mswing->_mp_d, ns);
              (x->_mp_size) = nx - (cy == 0);
            }
          while (s != 0);
        }
    }
}

Compile with the default compiler (claimed as 4.1.3) using -O
and no other flags.  This code is generated for the first part
of miscompiled_function:

miscompiled_function:
        .word 0xfc0
        subl2 $60,%sp
        cmpl 8(%ap),$16
        jlequ .L4
        cmpl 8(%ap),$399
        jgtru .L6
        movl 8(%ap),%r4
        clrl -60(%fp)
        jbr .L8
.L4:
        movl 8(%ap),%r0
        movl __gmp_oddfac_table[%r0],*8(%r0)               BAD
        movl 4(%ap),%r1
        movl $1,4(%r1)
        ret

The line annotated BAD stores in a completely invalid place,
related to the (non-pointer!) argument n.  Note that the source
operand is valud, using n properly.

It is fairly easy to make the compiler generate valid code by
making innocent changes to this file.

>Fix:
I have not made any attempt at fixing this compiler bug, since
I feel gcc 4.1 is obsolete.

If I were you, I'd upgrade to a current GCC version.  I notice
that your fear of GPL 3 seems limited given that the binutils
of this install is quite new, so GPL 3 must not be a valid
reason for staying obsolete with GCC.

>Release-Note:

>Audit-Trail:

Responsible-Changed-From-To: bin-bug-people->toolchain-manager
Responsible-Changed-By: wiz@NetBSD.org
Responsible-Changed-When: Sun, 09 Dec 2012 16:10:37 +0000
Responsible-Changed-Why:
toolchain problem
(vax is the only port which still uses gcc-4.1, other ports
are already using 4.5)


From: Martin Husemann <martin@duskware.de>
To: gnats-bugs@NetBSD.org
Cc: 
Subject: Re: bin/47301: Miscompilation by bundled GCC
Date: Sun, 9 Dec 2012 21:19:43 +0100

 Newer gcc are even worse for vax in our experience, which made us
 downgrade to 4.1 in the first place.

 Please try to reproduce the problem with a modern gcc and file a bug
 report upstream - or let us know which newer version fixes it.

 We are likely to upgrade gcc for all arches where it works to 4.7.x sometime
 soon.

 Martin

From: Torbjorn Granlund <tg@gmplib.org.dontsendmailthere>
To: gnats-bugs@NetBSD.org
Cc: toolchain-manager@netbsd.org, gnats-admin@netbsd.org,
	 netbsd-bugs@netbsd.org
Subject: Re: bin/47301: Miscompilation by bundled GCC
Date: Mon, 10 Dec 2012 14:10:36 +0100

 Martin Husemann <martin@duskware.de> writes:

    Newer gcc are even worse for vax in our experience, which made us
    downgrade to 4.1 in the first place.
 =20=20=20
 I see.

    Please try to reproduce the problem with a modern gcc and file a bug
    report upstream - or let us know which newer version fixes it.

 I tried gcc 4.7.2, and it also generates bad code.  It is probably a bug
 in the vax port.

 (I cannot report this to GCC, as they require me to create an account.
 I will not.  They bug reports mailing list seem dead.)

    We are likely to upgrade gcc for all arches where it works to 4.7.x some=
 time
    soon.

 Good that you keep up with GCC releases!

 --=20
 Torbj=C3=B6rn

From: Torbjorn Granlund <tg@gmplib.org.dontsendmailthere>
To: gnats-bugs@NetBSD.org
Cc: toolchain-manager@netbsd.org, gnats-admin@netbsd.org,
	 netbsd-bugs@netbsd.org
Subject: Re: bin/47301: Miscompilation by bundled GCC
Date: Mon, 10 Dec 2012 15:22:41 +0100

 I looked a bit into this GCC problem, using gcc 4.7.2.

 It seems to be a reload problem, and I think the vax port is innocent.

 We have (slightly edited for legibility),

   (set (mem:SI (mem/f:SI (plus:SI (reg/v/f:SI 261 [ x ])
 				  (const_int 8))))
        (mem/u:SI (plus:SI (mult:SI (reg/v:SI 262 [ n ])
 				   (const_int 4))
 			  (symbol_ref:SI ("__gmp_oddfac_table")))))

 which then gets reloaded into,

   (set (reg:SI 1 %r1)
        (mem/f/c:SI (plus:SI (reg/f:SI 12 %ap)
 			    (const_int 4))))

   (set (reg:SI 1 %r1)
        (mem/c:SI (plus:SI (reg/f:SI 12 %ap)
 			  (const_int 8))))

   (set (mem:SI (mem/f:SI (plus:SI (reg:SI 1 %r1)
 				  (const_int 8))))
        (mem/u:SI (plus:SI (mult:SI (reg:SI 1 %r1)
 				   (const_int 4))
 			  (symbol_ref:SI ("__gmp_oddfac_table")))))

 i.e., reload puts both pseudo 261 and pseudo 262 into hard reg 1 in
 the same live range.  That is bad.

 Very few current backends support mem-to-mem copying in a single
 instruction.  It might be something that no longer works in reload.

 Assuming my assumption is correct, a possible fix would be to disallow
 mem-to-mem insns, at least until reload.

 --=20
 Torbj=C3=B6rn

From: <Paul_Koning@Dell.com>
To: <tg@gmplib.org.dontsendmailthere>
Cc: <gnats-bugs@NetBSD.org>, <toolchain-manager@netbsd.org>,
	<gnats-admin@netbsd.org>, <netbsd-bugs@netbsd.org>
Subject: Re: bin/47301: Miscompilation by bundled GCC
Date: Mon, 10 Dec 2012 16:37:07 +0000

 On Dec 10, 2012, at 9:22 AM, Torbjorn Granlund wrote:

 > I looked a bit into this GCC problem, using gcc 4.7.2.
 >=20
 > It seems to be a reload problem, and I think the vax port is innocent.
 >=20
 > We have (slightly edited for legibility),
 >=20
 >  (set (mem:SI (mem/f:SI (plus:SI (reg/v/f:SI 261 [ x ])
 > 				  (const_int 8))))
 >       (mem/u:SI (plus:SI (mult:SI (reg/v:SI 262 [ n ])
 > 				   (const_int 4))
 > 			  (symbol_ref:SI ("__gmp_oddfac_table")))))
 >=20
 > which then gets reloaded into,
 >=20
 >  (set (reg:SI 1 %r1)
 >       (mem/f/c:SI (plus:SI (reg/f:SI 12 %ap)
 > 			    (const_int 4))))
 >=20
 >  (set (reg:SI 1 %r1)
 >       (mem/c:SI (plus:SI (reg/f:SI 12 %ap)
 > 			  (const_int 8))))
 >=20
 >  (set (mem:SI (mem/f:SI (plus:SI (reg:SI 1 %r1)
 > 				  (const_int 8))))
 >       (mem/u:SI (plus:SI (mult:SI (reg:SI 1 %r1)
 > 				   (const_int 4))
 > 			  (symbol_ref:SI ("__gmp_oddfac_table")))))
 >=20
 > i.e., reload puts both pseudo 261 and pseudo 262 into hard reg 1 in
 > the same live range.  That is bad.
 >=20
 > Very few current backends support mem-to-mem copying in a single
 > instruction.  It might be something that no longer works in reload.
 >=20
 > Assuming my assumption is correct, a possible fix would be to disallow
 > mem-to-mem insns, at least until reload.
 >=20
 > --=20
 > Torbj=F6rn

 I wonder what that workaround would do to performance.  This sort of reload=
  case could pop up in lots of machine architectures -- any CISC-like machin=
 e might be affected.  pdp11, 68k, i386, ...

 	paul

From: David Laight <david@l8s.co.uk>
To: gnats-bugs@NetBSD.org
Cc: 
Subject: Re: bin/47301: Miscompilation by bundled GCC
Date: Mon, 10 Dec 2012 19:48:40 +0000

 On Mon, Dec 10, 2012 at 04:40:04PM +0000, Paul_Koning@Dell.com wrote:
 >  
 > I wonder what that workaround would do to performance.
 > This sort of reload case could pop up in lots of machine
 > architectures -- any CISC-like machine might be affected.
 > pdp11, 68k, i386, ...

 pdp11 is only 16bit.
 i386 only allows one memory operand (except for special instructions
     with fixed registers.
 m68k does allow memory-memory oparations (if I've read the book properly).

 	David

 -- 
 David Laight: david@l8s.co.uk

From: <Paul_Koning@Dell.com>
To: <gnats-bugs@NetBSD.org>
Cc: <toolchain-manager@netbsd.org>, <gnats-admin@netbsd.org>,
	<netbsd-bugs@netbsd.org>, <tg@gmplib.org.dontsendmailthere>
Subject: Re: bin/47301: Miscompilation by bundled GCC
Date: Mon, 10 Dec 2012 19:37:01 +0000

 On Dec 10, 2012, at 2:35 PM, David Laight wrote:

 > The following reply was made to PR bin/47301; it has been noted by GNATS.
 >=20
 > From: David Laight <david@l8s.co.uk>
 > To: gnats-bugs@NetBSD.org
 > Cc:=20
 > Subject: Re: bin/47301: Miscompilation by bundled GCC
 > Date: Mon, 10 Dec 2012 19:48:40 +0000
 >=20
 > On Mon, Dec 10, 2012 at 04:40:04PM +0000, Paul_Koning@Dell.com wrote:
 >>=20
 >> I wonder what that workaround would do to performance.
 >> This sort of reload case could pop up in lots of machine
 >> architectures -- any CISC-like machine might be affected.
 >> pdp11, 68k, i386, ...
 >=20
 > pdp11 is only 16bit.

 True but it still sees SI operands.  For that matter, I'm assuming it could=
  see the identical scenario if the arguments are HImode (which then matches=
  its register size).

 > i386 only allows one memory operand (except for special instructions
 >     with fixed registers.
 > m68k does allow memory-memory oparations (if I've read the book properly)=
 .

From: christos@zoulas.com (Christos Zoulas)
To: gnats-bugs@NetBSD.org, toolchain-manager@netbsd.org, 
	gnats-admin@netbsd.org, netbsd-bugs@netbsd.org, tg@gmplib.org.dontsendmailthere
Cc: 
Subject: Re: bin/47301: Miscompilation by bundled GCC
Date: Mon, 10 Dec 2012 15:37:59 -0500

 On Dec 10,  4:40pm, Paul_Koning@Dell.com (<Paul_Koning@Dell.com>) wrote:
 -- Subject: Re: bin/47301: Miscompilation by bundled GCC

 |  > i.e., reload puts both pseudo 261 and pseudo 262 into hard reg 1 in
 |  > the same live range.  That is bad.
 |  >
 |  > Very few current backends support mem-to-mem copying in a single
 |  > instruction.  It might be something that no longer works in reload.
 |  >
 |  > Assuming my assumption is correct, a possible fix would be to disallow
 |  > mem-to-mem insns, at least until reload.

 Yes, but that dissallowing should happen in the MI code not in the backends,
 right? If so, do you know how to do it/where to put it?

 christos

From: Torbjorn Granlund <tg@gmplib.org.dontsendmailthere>
To: gnats-bugs@NetBSD.org
Cc: toolchain-manager@netbsd.org, gnats-admin@netbsd.org,
	 netbsd-bugs@netbsd.org
Subject: Re: bin/47301: Miscompilation by bundled GCC
Date: Mon, 10 Dec 2012 21:41:33 +0100

 christos@zoulas.com (Christos Zoulas) writes:

   The following reply was made to PR bin/47301; it has been noted by GNATS.
 =20=20
   From: christos@zoulas.com (Christos Zoulas)
   To: gnats-bugs@NetBSD.org, toolchain-manager@netbsd.org,=20
   	gnats-admin@netbsd.org, netbsd-bugs@netbsd.org, tg@gmplib.org
   Cc:=20
   Subject: Re: bin/47301: Miscompilation by bundled GCC
   Date: Mon, 10 Dec 2012 15:37:59 -0500
 =20=20
    On Dec 10,  4:40pm, Paul_Koning@Dell.com (<Paul_Koning@Dell.com>) wrote:
    -- Subject: Re: bin/47301: Miscompilation by bundled GCC
 =20=20=20
    |  > i.e., reload puts both pseudo 261 and pseudo 262 into hard reg 1 in
    |  > the same live range.  That is bad.
    |  >
    |  > Very few current backends support mem-to-mem copying in a single
    |  > instruction.  It might be something that no longer works in reload.
    |  >
    |  > Assuming my assumption is correct, a possible fix would be to disal=
 low
    |  > mem-to-mem insns, at least until reload.
 =20=20=20
    Yes, but that dissallowing should happen in the MI code not in the backe=
 nds,
    right? If so, do you know how to do it/where to put it?
 =20=20=20
 No, in vax.md.=20=20

 --=20
 Torbj=C3=B6rn

From: coypu@SDF.ORG
To: gnats-bugs@netbsd.org
Cc: 
Subject: Re: kern/47301: firmware download page in bwi(4) isn't reachable
Date: Tue, 8 Nov 2016 19:18:46 +0000

 This particular one is extra problematic. I'm pretty sure
 it's not legal to distribute it... so rehosting it is a
 problem.

From: coypu@SDF.ORG
To: gnats-bugs@netbsd.org
Cc: 
Subject: Re: kern/47301: firmware download page in bwi(4) isn't reachable
Date: Tue, 8 Nov 2016 19:21:55 +0000

 Sorry for the noise, wrong PR number!

>Unformatted:

Home	PR Database Search