Help, I have error: unable to find a register to spill in class 'POINTER_REGS'

Projects Programming
1

Hi Guys,

I'm working on a project where I need to take 1024 samples from an ADC and do an FFT of the data. I have a working program on the Raspberry Pi and wanted to just port the C code from there to the Arduino so I copied and pasted in the FFT routine However, it wont compile and I just get the following error: unable to find a register to spill in class 'POINTER_REGS' so I went through the code commenting out line by line to see where the faiult lies and there are two lines which if commented out, will compile. This is the code

void dofft(double *xreal,int n)
{
  int n0, k0 = 0, sby2, p, q, s, index, jndex, itemp, i, j, l;
  static int first_call_flag = 1, l2n;
  static double gain, angle, re, im;
  double xtempreal, xtempimag, treal, timag, vreal, vimag;
  double wreal, wimag, temp, wrtemp, *ximag,*ureal,*uimag;
  
  ximag = (double *) calloc(2*n+1,sizeof(double));
  ureal = (double *) calloc(n/2+1,sizeof(double));
  uimag = (double *) calloc(n/2+1,sizeof(double));

  if (ximag == NULL || ureal == NULL || uimag == NULL) abort(); 


  if ( first_call_flag == 1)
  {
    l2n = 0;
    n0 = 1;
    do
    {
      l2n += 1;
      n0 = n0 + n0;
    }
    while (n0 < n);
    gain = 1.0 / n;
    angle = 2.0 * M_PI * gain;
    re = cos(angle);
    im = sin(angle);
  }

  /* Compute the complex exponentials if this is the first call */
  if (first_call_flag ==1 && k0 < 1)
  {
    ureal[1] = re;
    uimag[1] = -fabs (im);
    for ( i = 2; i <= l2n; ++i )
    {
      ureal[i] = ureal[i-1] * ureal[i-1] - uimag[i-1] * uimag[i-1];
      uimag[i] = 2. * ureal[i-1] * uimag[i-1];
    }
    k0 = 1;
  }

  /**************** Main loop ****************/
  sby2 = n;
  for ( j = 1; j <= l2n; ++j )
  {
    vreal = ureal[j];
    vimag = uimag[j];
    wreal = 1;
    wimag = 0;
    s = sby2;
    sby2 = s / 2;
    for ( l = 1; l <= sby2; ++l )
    {
      for ( i = 1; i <= n; i = i + s )
      {
        p = i + l - 1;
        q = p + sby2;
        treal = xreal[p] + xreal[q];
        timag = ximag[p] + ximag[q];
        temp = xreal[q];
        xreal[q] = (xreal[p] - xreal[q]) * wreal - (ximag[p] - ximag[q]) * wimag;
        ximag[q] = (ximag[p] - ximag[q]) * wreal + (xreal[p] - temp) * wimag;
        xreal[p] = treal;
        ximag[p] = timag;
      }
      wrtemp = wreal;
      wreal=wreal*vreal-wimag*vimag;
      wimag=wrtemp*vimag+wimag*vreal;

    }
  } 
  /* Reorder the elements using bit reversal */
  for ( i = 1; i <= n; ++i )
  {
    index = i - 1;
    jndex = 0;
    for ( j = 1; j <= l2n; ++j )
    {
      jndex = jndex + jndex;
      itemp = index / 2;
      if ( itemp + itemp != index) jndex +=1;
      index = itemp;
    }
    j = jndex + 1;
    if ( j >= i)
    {
      xtempreal = xreal[j];
      xtempimag = ximag[j];
      xreal[j] = xreal[i];
      ximag[j] = ximag[i];
      xreal[i] = xtempreal;
      ximag[i] = xtempimag;
    }
  }

  for ( i = 1; i <= n; ++i ) 
    xreal[n+i] = ximag[i];

  for( i=1; i<=n; i++ )                  
    xreal[i]=absolute( xreal[i],ximag[i])*gain;
  
  free(uimag);
  free(ureal);
  free(ximag);
}

and if I comment out

wreal=wrealvreal-wimagvimag;
wimag=wrtempvimag+wimagvreal;

it will compile but obviously not to the fft correctly.

The full error message is

C:\Users\Steve\Documents\Arduino\ADCFFT\ADCFFT.ino: In function 'void dofft(double*, int)':

ADCFFT:162: error: unable to find a register to spill in class 'POINTER_REGS'

 }

 ^

ADCFFT:162: error: this is the insn:

(insn 163 162 165 15 (set (reg/v:SF 89 [ vreal ])

        (mem:SF (post_inc:HI (reg:HI 157 [ ivtmp.141 ])) [3 MEM[base: _96, offset: 0B]+0 S4 A8])) C:\Users\Steve\Documents\Arduino\ADCFFT\ADCFFT.ino:103 99 {*movsf}

     (expr_list:REG_INC (reg:HI 157 [ ivtmp.141 ])

        (nil)))

C:\Users\Steve\Documents\Arduino\ADCFFT\ADCFFT.ino:162: confused by earlier errors, bailing out

Using library MCP3208 in folder: C:\Users\Steve\Documents\Arduino\libraries\MCP3208 (legacy)
Using library SPI at version 1.0 in folder: C:\Program Files (x86)\Arduino\hardware\arduino\avr\libraries\SPI 
exit status 1
unable to find a register to spill in class 'POINTER_REGS'

Now, I've googled this problem and found may instances and several remedies but none that have worked for me. Can anyone please throw any light on the matter?

Thanks, Steve.

2

That's a deep internal compiler error to do with register allocation of variables in a function
in the code-generation phase.

Are you aware that the regular Arduino Uno has only 2k of RAM in total? Or is this for a larger
board? And that floating point is done in software and slow. People often used fixed point
arithmetic for compute-intensive stuff on microcontrollers.

I suspect that the issue is perhaps triggered by the large numbers of doubles (which are treated
as float on most Arduinos), perhaps some compiler limit has been hit.

My other comment is do you want an FFT or a FDCT (4 times faster, 1/2 the storage). If you have
limited CPU cycles to throw at the problem, and you aren't processing complex signals or interested
in phases, a FDCT is the way to go.

3

I had that happen once. I split up the offending statements and it worked.
Try this:

      wreal=wreal*vreal;
      wreal -= wimag*vimag;
      wimag=wrtemp*vimag
      wimag += wimag*vreal;

Pete

4

P.S. If that doesn't work, try splitting up the calculation of xreal[q] and ximag[q] inside the for loops.

Pete

5

@MarkT, thanks for your suggestion. I maybe should have said that I'm using a mega2560 for the increased memory however, I don't think that's the issue because when I comment out those lines and it does compile, it uses very little memory.

Let me explain a little bit more about my project. I'm using an accelerometer to measure vibration. I want to calculate the overall velocity levels between 10-1000hz. Now to do that, I want to take 1024 samples at a rate of 2560 samples per second or 1 sample every 391uSec. I have that bit sussed. Then I do an fft of the TWF (time waveform) which would give me a 512 line spectrum from 0-1230hz. dropping off the upper 112 lines gives me a 400 line spectrum from 0-1000hz in acceleration G's From that, I can integrate to Velocity in mm/sec, ignore the first 4 lines and calculate the overall (ISO) level.

I'm still at the suck it and see stage so I am happy to drop the spectra size to 200, 100 or even 50 lines if necessary - it's just to give me an indication of overall velocity - if this indicates high vibration levels, then I will take a higher resolution TWF which will be analysed on a PC capable of handling many more calculations in a second than the Arduino does in a day (well, almost).

Do you think the FDCT would be appropriate for this purpose and if so, can you point me to some code, or a library. I'm afraid the wiki page you sent me to might as well be Chinese to me.

@Pete, thanks to you also. Your first suggestion failed and I'm not sure my maths skills are up to the second one

6

it uses very little memory.

The compilation report knows nothing about memory that is malloced.

7

AWOL:
The compilation report knows nothing about memory that is malloced.

Awol, I appreciate that because it doesn't get malloced until runtime and I expect that it would crash the program at run time if I tried to malloc too much, rather than at compile time. If I was getting as far as runtime, Id be happier!

Thanks for the comment though.

8 
        xreal[q] = (xreal[p] - xreal[q]) * wreal;
        xreal[q] -= (ximag[p] - ximag[q]) * wimag;
        ximag[q] = (ximag[p] - ximag[q]) * wreal;
        ximag[q] += (xreal[p] - temp) * wimag;

Pete

9

Thanks Pete but Noooooooo it still doesn't work Aaargghhhhh

10

I got it to compile by extracting the code from the inner for loop and putting it into a separate function. This will slow down execution but at least it compiles now. I have no way of testing this. Hope it works.

Pete

void inner_loop(int l,int sby2,int n, int s,double *xreal,double *ximag, double& vreal,double& wimag , double& wreal, double& vimag)
{
  int i,p,q;
  double wrtemp,treal,timag,temp;
      for ( i = 1; i <= n; i = i + s )
      {
        p = i + l - 1;
        q = p + sby2;
        treal = xreal[p] + xreal[q];
        timag = ximag[p] + ximag[q];
        temp = xreal[q];
        xreal[q] = (xreal[p] - xreal[q]) * wreal - (ximag[p] - ximag[q]) * wimag;
        ximag[q] = (ximag[p] - ximag[q]) * wreal + (xreal[p] - temp) * wimag;
        xreal[p] = treal;
        ximag[p] = timag;
      }
      wrtemp = wreal;
      wreal=wreal*vreal-wimag*vimag;
      wimag=wrtemp*vimag+wimag*vreal;
}

void dofft(double *xreal,int n)
{
// I have commented a few variables which are only used in the new function
  int n0, k0 = 0, sby2,/* p, q, */s, index, jndex, itemp, i, j, l;
  static int first_call_flag = 1, l2n;
  static double gain, angle, re, im;
  double xtempreal, xtempimag, /*treal, timag,*/ vreal, vimag;
  double wreal, wimag,/* temp, wrtemp,*/ *ximag,*ureal,*uimag;
 
  ximag = (double *) calloc(2*n+1,sizeof(double));
  ureal = (double *) calloc(n/2+1,sizeof(double));
  uimag = (double *) calloc(n/2+1,sizeof(double));

  if (ximag == NULL || ureal == NULL || uimag == NULL) abort();


  if ( first_call_flag == 1)
  {
    l2n = 0;
    n0 = 1;
    do
    {
      l2n += 1;
      n0 = n0 + n0;
    }
    while (n0 < n);
    gain = 1.0 / n;
    angle = 2.0 * M_PI * gain;
    re = cos(angle);
    im = sin(angle);
  }

  /* Compute the complex exponentials if this is the first call */
  if (first_call_flag ==1 && k0 < 1)
  {
    ureal[1] = re;
    uimag[1] = -fabs (im);
    for ( i = 2; i <= l2n; ++i )
    {
      ureal[i] = ureal[i-1] * ureal[i-1] - uimag[i-1] * uimag[i-1];
      uimag[i] = 2. * ureal[i-1] * uimag[i-1];
    }
    k0 = 1;
  }

  /**************** Main loop ****************/
  sby2 = n;
  for ( j = 1; j <= l2n; ++j )
  {
    vreal = ureal[j];
    vimag = uimag[j];
    wreal = 1;
    wimag = 0;
    s = sby2;
    sby2 = s / 2;
    for ( l = 1; l <= sby2; ++l )
    {
// Move this code to a separate function
/*
      for ( i = 1; i <= n; i = i + s )
      {

        p = i + l - 1;
        q = p + sby2;
        treal = xreal[p] + xreal[q];
        timag = ximag[p] + ximag[q];
        temp = xreal[q];
        xreal[q] = (xreal[p] - xreal[q]) * wreal - (ximag[p] - ximag[q]) * wimag;
        ximag[q] = (ximag[p] - ximag[q]) * wreal + (xreal[p] - temp) * wimag;
        xreal[p] = treal;
        ximag[p] = timag;
      }
      wrtemp = wreal;
      wreal=wreal*vreal-wimag*vimag;
      wimag=wrtemp*vimag+wimag*vreal;
*/
      inner_loop(l,sby2,n,s,xreal,ximag,vreal,wimag ,wreal,vimag);
    }
  }
  /* Reorder the elements using bit reversal */
  for ( i = 1; i <= n; ++i )
  {
    index = i - 1;
    jndex = 0;
    for ( j = 1; j <= l2n; ++j )
    {
      jndex = jndex + jndex;
      itemp = index / 2;
      if ( itemp + itemp != index) jndex +=1;
      index = itemp;
    }
    j = jndex + 1;
    if ( j >= i)
    {
      xtempreal = xreal[j];
      xtempimag = ximag[j];
      xreal[j] = xreal[i];
      ximag[j] = ximag[i];
      xreal[i] = xtempreal;
      ximag[i] = xtempimag;
    }
  }

  for ( i = 1; i <= n; ++i )
    xreal[n+i] = ximag[i];

  for( i=1; i<=n; i++ )                 
    xreal[i]=absolute( xreal[i],ximag[i])*gain;
 
  free(uimag);
  free(ureal);
  free(ximag);
}
11

@Pete,

Thanks for that. I'll test it out later when I get the chance.

If you're ever in Paphos, Cyprus there's an ice cold bottle of Keo waiting for you. You deserve it!

Steve.

12

CM_Guy:
@Pete,

If you're ever in Paphos, Cyprus there's an ice cold bottle of Keo waiting for you. You deserve it!

Make that a crate - it works....

However, I am limited to only throwing 256 samples at it which is fine for what I want.

Cheers.

13

Glad it worked.
Much as I would like to pick up that beer, it isn't very likely I'll ever get to Cyprus. Thanks for the Karma though :slight_smile:

Pete

14

I don't understand why you would switch to the frequency domain to measure the vibration.

Just digitally filter to get a band-width limited signal in 10 -- 1000Hz range and then compute
directly. This also allows a much more real-time read out of the statistic you want.

Digital filtering can be a lot less expensive than FFT or even DCT. You'd probably want to sample at a
higher rate to get easy filter design, say 5kHz or so. First use RC low pass to anti-alias with a cutoff
about 2kHz, sample at 5kHz or more and a simple 4 pole low pass filter down to 1kHz.

Since you are interested in measurement of these energies you would have had to tackle the anti-aliasing
issue anyway (sampling at 2.56kHz without analog filter will alias frequencies above 2.56k down onto
the sampled signal).

Pass through a 2 pole high-pass (10Hz), to get you bandwidth limited signal.