[Alpha] ICE in insert_save_restore

[Robert Harley <Robert dot Harley at inria dot fr>]

Situation:
----------

EGCS 1.1.2 on Alpha Linux, configured with:

  configure alphaev5-unknown-linux-gnulibc1 --enable-haifa

It works fine, usually.


Problem:
--------

With code appended below, get:

  egcs -O3 -c bug.c -DWHICH=1
  OK

  egcs -O2 -c bug.c -DWHICH=2
  OK

  egcs -O3 -c bug.c -DWHICH=2
  ../../egcs-1.1.2/gcc/caller-save.c:657: Internal compiler error in function insert_save_restore


The problem appears to be related to a constant in some small functions
that get inlined.  If it's above 32768, boom.

The example is a bit long, circa 250 lines, distilled from a much
bigger program.  The problem seems to be very fragile i.e., deleting
just about any piece of code anywhere can make the ICE disappear.


It took a lot of work to narrow it down this far... hope somebody can
take it further.

Bye,
  Rob.

-- Cut here ------------------------------------------------------------------

/* Copyright (c) Robert Harley 1999.

egcs -O3 -c bug.c -DWHICH=1
OK

egcs -O2 -c bug.c -DWHICH=2
OK

egcs -O3 -c bug.c -DWHICH=2
../../egcs-1.1.2/gcc/caller-save.c:657: Internal compiler error in function insert_save_restore

*/

#warning FOR I.C.E. DEMO ONLY.  PLEASE DO NOT USE FOR OTHER STUFF.

#ifndef __alpha
#error This is for Alpha only!
#endif


/*== #includes =============================================================*/

#include <assert.h>


/*== #defines ==============================================================*/

#if WHICH == 1
#define PRIME (32749UL)
#elif WHICH == 2
#define PRIME (32771UL)
#else
#error Please define WHICH to be 1 or 2.
#endif

#define CURVE { { 1597UL, 1041UL, 5503UL, 6101UL, 1887UL } }

#define IDENTITY { { 0UL, 0UL, 1UL}, { 0UL, 0UL } }


/*== Types =================================================================*/

typedef unsigned long elem;

typedef struct { elem c1; } monicLinearPoly;
typedef struct { elem c0, c1; } linearPoly;
typedef struct { elem c0, c1, c2; } quadraticPoly;
typedef struct { elem c1, c2, c3; } monicCubicPoly;
typedef struct { elem c1, c2, c3, c4, c5; } monicQuinticPoly;

typedef struct { monicQuinticPoly f; } curve;

typedef struct { quadraticPoly u; linearPoly v; } divisor;


/*== Function declarations =================================================*/

static elem sum(elem x, elem y);
static elem half(elem x);
static elem minus(elem x);
static elem diff(elem x, elem y);
static elem product(elem x, elem y);
static elem square(elem x);
static elem inverse(elem x);
static elem quotient(elem x, elem y);

static divisor thetaDouble
  (const elem x, const elem y, const curve C);
static divisor bla1
  (const divisor D, const quadraticPoly nu, const linearPoly s);
static monicCubicPoly bla2
  (const divisor D, const curve C, elem v0sq, elem v0v1, elem v1sq);
static divisor jacobianDouble
  (const divisor D, const curve C);


/*== Function definitions ==================================================*/

/*-- sum -------------------------------------------------------------------*/

/* Sum x+y. */
static elem sum(elem x, elem y) {
  elem s;
  const elem pr = PRIME;

  s = x+y;
  if (x >= pr-y) s -= pr;

  return s;
} /* end sum */


/*-- diff ------------------------------------------------------------------*/

/* Returns difference x-y. */
static elem diff(elem x, elem y) {
  elem d;
  const elem pr = PRIME;

  d = x-y;
  if (x < y) d += pr;

  return d;
} /* end diff */


/*-- product ---------------------------------------------------------------*/

/* Returns x*y. */
static elem product(elem x, elem y) {
  const elem pr = PRIME;

  return x*y % pr;
} /* end product */


/*-- quotient --------------------------------------------------------------*/

/* Returns x/y for y != 0. */
static elem quotient(elem x, elem y) {

  return product(x, inverse(y));
} /* end quotient */


/*-- jacobianDouble --------------------------------------------------------*/

/* Double an arbitrary divisor. */
static divisor jacobianDouble(const divisor D, const curve C) {
  const divisor identity = IDENTITY;

  if (D.u.c0) {
    assert(D.u.c0 == 1UL);

    if (!D.v.c0 && !D.v.c1) return identity;
    else {
      elem denom, v0sq, v0v1, v1sq;

      v0sq = square(D.v.c0);
      v0v1 = product(D.v.c0, D.v.c1);
      v1sq = square(D.v.c1);

      denom = sum(diff(product(D.u.c2, v0sq), product(D.u.c1, v0v1)), v1sq);

      if (!denom) {
        elem mx0, x1,y1;

        assert(D.v.c0 != 0UL);
        mx0 = quotient(D.v.c1, D.v.c0);

        assert(!diff(D.u.c2, product(diff(D.u.c1, mx0), mx0)));

        x1 = diff(mx0, D.u.c1);
        y1 = sum(product(D.v.c0, x1), D.v.c1);
        assert(y1 != 0UL);

        return thetaDouble(x1, y1, C);
      } else {
        linearPoly iv, s;
        monicCubicPoly k;
        monicLinearPoly l;

        { elem invDenom;

          invDenom = inverse(denom);
          iv.c0 = minus(product(D.v.c0, invDenom));
          iv.c1 = product(diff(D.v.c1, product(D.u.c1, D.v.c0)), invDenom);
        } /* end block */

        k = bla2(D, C, v0sq, v0v1, v1sq);

        { linearPoly kmu;

          { monicCubicPoly t1;

            t1.c1 = diff(k.c1, D.u.c1);
            t1.c2 = diff(k.c2, D.u.c2);

            t1.c2 = diff(t1.c2, product(t1.c1, D.u.c1));
            t1.c3 = diff(k.c3, product(t1.c1, D.u.c2));

            kmu.c0 = t1.c2;
            kmu.c1 = t1.c3;
          } /* end block */

          { quadraticPoly t2;

            t2.c0 = product(kmu.c0, iv.c0);
            t2.c2 = product(kmu.c1, iv.c1);
            t2.c1 = product(sum(kmu.c0, kmu.c1), sum(iv.c1, iv.c0));
            t2.c1 = diff(diff(t2.c1, t2.c0), t2.c2);

            t2.c1 = diff(t2.c1, product(t2.c0, D.u.c1));
            t2.c2 = diff(t2.c2, product(t2.c0, D.u.c2));

            s.c0 = t2.c1;
            s.c1 = t2.c2;
          } /* end block */
        } /* end block */

        { quadraticPoly sv;

          sv.c0 = product(s.c0, D.v.c0);
#ifndef NDEBUG
          sv.c1 = sum(product(s.c0, D.v.c1), product(s.c1, D.v.c0));
          sv.c2 = product(s.c1, D.v.c1);
#endif

          k.c1 = diff(k.c1, sv.c0);
#ifndef NDEBUG
          k.c2 = diff(k.c2, sv.c1);
          k.c3 = diff(k.c3, sv.c2);
#endif

          k.c1 = diff(k.c1, D.u.c1);
#ifndef NDEBUG
          k.c2 = diff(k.c2, D.u.c2);

          k.c2 = diff(k.c2, product(k.c1, D.u.c1));
          assert(!k.c2);
          k.c3 = diff(k.c3, product(k.c1, D.u.c2));
          assert(!k.c3);
#endif

          l.c1 = k.c1;
        } /* end block */

        s.c0 = half(s.c0);
        s.c1 = half(s.c1);

        { quadraticPoly nu;

          nu.c0 = square(s.c0);
          nu.c2 = square(s.c1);
          { elem t;

            t = square(sum(s.c0, s.c1));
            nu.c1 = diff(diff(t, nu.c0), nu.c2);
          } /* end block */

          nu.c2 = diff(nu.c2, l.c1);

          return bla1(D, nu, s);
        } /* end block */
      } /* end if/else */

    } /* end if/else */

  } else if (D.u.c1) {
    elem mxp,yp;

    assert(D.u.c1 == 1UL);
    mxp = D.u.c2;
    assert(!D.v.c0);
    yp = D.v.c1;

    return thetaDouble(mxp, yp, C);
  } else {
    assert(D.u.c2 == 1UL);
    assert(!D.v.c0 && !D.v.c1);

    return identity;
  } /* end if/else if/else */

} /* end jacobianDouble */