gcc 2.95.3 [not pre-3.x]: gmp powm incorrect i686 code

[Kevin Ryde <user42 at zip dot com dot au>]

This bug, as far as I can tell, doesn't occur in the current gcc cvs.
I say i686 in the subject because removing -march=pentiumpro from the
flags makes the bug disappear and because the problem is near a p-pro
cmov, but actually I've got no idea whether this is relevant or merely
a coincidence.


Using a Debian i386 packaged gcc 2.95.3,

    Reading specs from /usr/lib/gcc-lib/i386-linux/2.95.3/specs
    gcc version 2.95.3 20010111 (prerelease)

(or 2.95.2 on Debian or FreeBSD), I believe the program below results
in incorrect assembler code when compiled with

    gcc -g -O -fomit-frame-pointer -march=pentiumpro -mcpu=pentiumpro \
       powm311.c

The statement

    j = (c->_mp_size >= 0 ? c->_mp_size : - c->_mp_size);

comes out as follows (from objdump), and I believe 0x20(%esp) is being
used uninitialized.

 804846d:       8b 56 04                mov    0x4(%esi),%edx
 8048470:       89 d0                   mov    %edx,%eax
 8048472:       f7 d8                   neg    %eax
 8048474:       83 7c 24 20 ff          cmpl   $0xffffffff,0x20(%esp,1)
 8048479:       0f 4f c2                cmovg  %edx,%eax
 804847c:       89 44 24 20             mov    %eax,0x20(%esp,1)

If you're lucky the whole program will print "j is -1" whereas it
ought to print "j is 1", but that will depend on the previous contents
of 0x20(%esp).  Under the debugger it can be seen the value there
certainly isn't c->_mp_size.

For what it's worth, the program is a cut-down part of powm.c from gmp
3.1.1.  It looks pretty horrible, but further simple minded chopping
seems to make the bug disappear.


struct mpz {
  int           _mp_alloc;
  int           _mp_size;
  unsigned long *_mp_d;
};

#define MPN_ZERO(DST, NLIMBS)                   \
  do {                                          \
    long __i;                              \
    for (__i = 0; __i < (NLIMBS); __i++)        \
      (DST)[__i] = 0;                           \
  } while (0)

#define MPN_NORMALIZE(DST, NLIMBS) \
  do {									\
    while (NLIMBS > 0)							\
      {									\
	if ((DST)[(NLIMBS) - 1] != 0)					\
	  break;							\
	NLIMBS--;							\
      }									\
  } while (0)

extern inline unsigned long
mpn_add_1 (register unsigned long       *res_ptr,
	   register const unsigned long *s1_ptr,
	   register long                s1_size,
	   register unsigned long       s2_limb)
{
  register unsigned long x;

  x = *s1_ptr++;
  s2_limb = x + s2_limb;
  *res_ptr++ = s2_limb;
  if (s2_limb < x)
    {
      while (--s1_size != 0)
	{
	  x = *s1_ptr++ + 1;
	  *res_ptr++ = x;
	  if (x != 0)
	    goto fin;
	}

      return 1;
    }

 fin:
  if (res_ptr != s1_ptr)
    {
      long i;
      for (i = 0; i < s1_size - 1; i++)
	res_ptr[i] = s1_ptr[i];
    }
  return 0;
}


void
mpz_redc (struct mpz *c,
          const struct mpz *a, const struct mpz *b, const struct mpz *m,
          unsigned long Nprim)
{
  unsigned long *cp;
  unsigned long *mp = m->_mp_d;
  unsigned long cy;
  unsigned long cout = 0;
  unsigned long q;
  unsigned j;
  unsigned n = (m->_mp_size >= 0 ? m->_mp_size : - m->_mp_size);

  noop (c, a, b);
  cp = c->_mp_d;

  j = (c->_mp_size >= 0 ? c->_mp_size : - c->_mp_size);
  printf ("j is %d\n", j);
  stop ();

  MPN_ZERO (cp + j, 2 * n - j);
  for (j = 0; j < n; j++)
    {
      q = cp[0] * Nprim;
      cy = noop (cp, mp, n, q);
      cout += mpn_add_1 (cp + n, cp + n, n - j, cy);
      cp++;
    }
  cp -= n;
  if (cout)
    {
      cy = cout - noop (cp, cp + n, mp, n);
      while (cy)
	cy -= noop (cp, cp, mp, n);
    }
  else
    noop (cp, cp + n, n);
  MPN_NORMALIZE (cp, n);
  c->_mp_size = c->_mp_size < 0 ? -n : n;
}


void noop() {}
void stop() { exit(0); }

int main (void)
{
  struct mpz  c, a, b, m;
  unsigned long  l;
  c._mp_d = &l;
  c._mp_size = -1;
  mpz_redc (&c, &a, &b, &m, 0);
}
# 1 "powm311.c"

struct mpz {
  int           _mp_alloc;
  int           _mp_size;
  unsigned long *_mp_d;
};









# 24 "powm311.c"

extern inline unsigned long
mpn_add_1 (register unsigned long       *res_ptr,
	   register const unsigned long *s1_ptr,
	   register long                s1_size,
	   register unsigned long       s2_limb)
{
  register unsigned long x;

  x = *s1_ptr++;
  s2_limb = x + s2_limb;
  *res_ptr++ = s2_limb;
  if (s2_limb < x)
    {
      while (--s1_size != 0)
	{
	  x = *s1_ptr++ + 1;
	  *res_ptr++ = x;
	  if (x != 0)
	    goto fin;
	}

      return 1;
    }

 fin:
  if (res_ptr != s1_ptr)
    {
      long i;
      for (i = 0; i < s1_size - 1; i++)
	res_ptr[i] = s1_ptr[i];
    }
  return 0;
}


void
mpz_redc (struct mpz *c,
          const struct mpz *a, const struct mpz *b, const struct mpz *m,
          unsigned long Nprim)
{
  unsigned long *cp;
  unsigned long *mp = m->_mp_d;
  unsigned long cy;
  unsigned long cout = 0;
  unsigned long q;
  unsigned j;
  unsigned n = (m->_mp_size >= 0 ? m->_mp_size : - m->_mp_size);

  noop (c, a, b);
  cp = c->_mp_d;

  j = (c->_mp_size >= 0 ? c->_mp_size : - c->_mp_size);
  printf ("j is %d\n", j);
  stop ();

  do { long __i; for (__i = 0; __i < (  2 * n - j ); __i++) ( cp + j )[__i] = 0; } while (0) ;
  for (j = 0; j < n; j++)
    {
      q = cp[0] * Nprim;
      cy = noop (cp, mp, n, q);
      cout += mpn_add_1 (cp + n, cp + n, n - j, cy);
      cp++;
    }
  cp -= n;
  if (cout)
    {
      cy = cout - noop (cp, cp + n, mp, n);
      while (cy)
	cy -= noop (cp, cp, mp, n);
    }
  else
    noop (cp, cp + n, n);
  do {	while (  n  > 0)	{	if (( cp )[(  n ) - 1] != 0)	break;	  n --;	}	} while (0) ;
  c->_mp_size = c->_mp_size < 0 ? -n : n;
}


void noop() {}
void stop() { exit(0); }

int main (void)
{
  struct mpz  c, a, b, m;
  unsigned long  l;
  c._mp_d = &l;
  c._mp_size = -1;
  mpz_redc (&c, &a, &b, &m, 0);
}