optimization/5120: tail recursion incorrect using -O2

[abbott@dima.unige.it]

>Number:         5120
>Category:       optimization
>Synopsis:       tail recursion incorrect using -O2
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Fri Dec 14 10:36:00 PST 2001
>Closed-Date:
>Last-Modified:
>Originator:     
>Release:        3.0.2
>Organization:
University of Genoa
>Environment:
System: Linux module.dima.unige.it 2.2.19-7.0.8 #1 Thu Jun 21 04:59:33 EDT 2001 i686 unknown
Architecture: i686 (actually an Athlon)

	
host: i686-pc-linux-gnu
build: i686-pc-linux-gnu
target: i686-pc-linux-gnu
configured with: ../gcc-3.0.2/configure 
>Description:
A tail recursive call to swap arguments is compiled wrongly with -O2
(seems to work OK with -O or no optimization).
Apparently with -O2 instead of swapping the args, one of the values
is duplicated (and the other lost).
>How-To-Repeat:
Compile attached file (BUG.c) using "gcc -O2 BUG.c" and run the resulting a.out.
The function DUPFFexgcd is called by main.  DUPFFexgcd tries to swap its two
pairs of args via tail recursion, a printf command shows that this clearly
does not happen.
>Fix:
I know no fix.

> C source:

typedef unsigned int FFelem;

FFelem FFmul(const FFelem x, const FFelem y)
{
  return x;
}


struct DUPFFstruct
{
  int maxdeg;
  int deg;
  FFelem *coeffs;
};

typedef struct DUPFFstruct *DUPFF;


int DUPFFdeg(const DUPFF f)
{
  return f->deg;
}


DUPFF DUPFFnew(const int maxdeg)
{
  DUPFF ans = (DUPFF)malloc(sizeof(struct DUPFFstruct));
  ans->coeffs = 0;
  if (maxdeg >= 0) ans->coeffs = (FFelem*)malloc((maxdeg+1)*sizeof(FFelem));
  ans->maxdeg = maxdeg;
  ans->deg = -1;
  return ans;
}

void DUPFFfree(DUPFF x)
{
}

void DUPFFswap(DUPFF x, DUPFF y)
{
}


DUPFF DUPFFcopy(const DUPFF x)
{
  return x;
}


void DUPFFshift_add(DUPFF f, const DUPFF g, int deg, const FFelem coeff)
{
}


DUPFF DUPFFexgcd(DUPFF *fcofac, DUPFF *gcofac, const DUPFF f, const DUPFF g)
{
  DUPFF u, v, uf, ug, vf, vg;
  FFelem q, lcu, lcvrecip, p;
  int df, dg, du, dv;

  printf("DUPFFexgcd called on degrees %d and %d\n", DUPFFdeg(f), DUPFFdeg(g));
  if (DUPFFdeg(f) < DUPFFdeg(g)) return DUPFFexgcd(gcofac, fcofac, g, f);  /*** BUG IN THIS LINE ***/
  if (f->coeffs[0] == 0) return f;
  /****** NEVER REACH HERE IN THE EXAMPLE ******/
  p = 2;

  df = DUPFFdeg(f);  if (df < 0) df = 0; /* both inputs are zero */
  dg = DUPFFdeg(g);  if (dg < 0) dg = 0; /* one input is zero */
  u = DUPFFcopy(f);
  v = DUPFFcopy(g);

  uf = DUPFFnew(dg); uf->coeffs[0] = 1; uf->deg = 0;
  ug = DUPFFnew(df);
  vf = DUPFFnew(dg);
  vg = DUPFFnew(df); vg->coeffs[0] = 1; vg->deg = 0;

  while (DUPFFdeg(v) > 0)
  {
    dv = DUPFFdeg(v);
    lcvrecip = FFmul(1, v->coeffs[dv]);
    while (DUPFFdeg(u) >= dv)
    {
      du = DUPFFdeg(u);
      lcu = u->coeffs[du];
      q = FFmul(lcu, lcvrecip);
      DUPFFshift_add(u, v, du-dv, p-q);
      DUPFFshift_add(uf, vf, du-dv, p-q);
      DUPFFshift_add(ug, vg, du-dv, p-q);
    }
    DUPFFswap(u, v);
    DUPFFswap(uf, vf);
    DUPFFswap(ug, vg);
  }
  if (DUPFFdeg(v) == 0)
  {
    DUPFFswap(u, v);
    DUPFFswap(uf, vf);
    DUPFFswap(ug, vg);
  }
  DUPFFfree(vf);
  DUPFFfree(vg);
  DUPFFfree(v);
  *fcofac = uf;
  *gcofac = ug;
  return u;
}



int main()
{
  DUPFF f, g, cf, cg, h;
  f = DUPFFnew(1); f->coeffs[1] = 1; f->deg = 1;
  g = DUPFFnew(2); g->coeffs[2] = 1; g->deg = 2;

  printf("calling DUPFFexgcd on degrees %d and %d\n", DUPFFdeg(f), DUPFFdeg(g)) ;
  h = DUPFFexgcd(&cf, &cg, f, g);
  return 0;
}

>Release-Note:
>Audit-Trail:
>Unformatted: