This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: type consistency of gimple


Hi Diego,

Jeff's point about our optimizers is also true.  Nick, remember that
issue with MIPS optimizations you were discussing with Jeff a few days
ago?  I didn't follow most of the details, but it involved ivopts and
sign issues.  Could you send a summary?

Sure:


I was looking at how a gcc 4.1 based compiler optimized a fast fourier transform algorithm for the MIPS target. What I found was the it was producing much worse code than a similarly configured gcc 3.4 based compiler, and the culprit was the creation of the induction variables used in the inner loop.

The nested loops look like this:

    signed short i,j,k,DataSizeExponent,DataSize;
    signed short RealBitRevData[MAX], ImagBitRevData[MAX];
    signed short * CosineV, * SineV;

    for (k = 1; k <= DataSizeExponent; k++)
    {
        signed short n1 = 1 << k;
        signed short n2 = n1 >> 1;
        signed short ArgIndex = 0;
        signed short DeltaIndex = (DataSize >> 1) / n2;

        for (j = 0; j < n2; j++)
        {
            signed int WReal = CosineV[ArgIndex];
	    signed int WImag = SineV[ArgIndex];

ArgIndex += DeltaIndex;
for (i = j; i < DataSize; i += n1)
{
signed short l = i + n2;
signed int tRealData = (WReal * RealBitRevData[l]) + (WImag * ImagBitRevData[l]);
signed int tImagData = (WReal * ImagBitRevData[l]) - (WImag * RealBitRevData[l]);


                tRealData = tRealData >> BUTTERFLY_SCALE_FACTOR;
                tImagData = tImagData >> BUTTERFLY_SCALE_FACTOR;
                RealBitRevData[l] = RealBitRevData[i] - tRealData;
                ImagBitRevData[l] = ImagBitRevData[i] - tImagData;
                RealBitRevData[i] += tRealData;
                ImagBitRevData[i] += tImagData;
            }
        }
    }

and the inner loop was being transformed into:

  short int D.2046, D.2043;
  long int D.2038, D.2035;
  int D.2033, D.2024,  D.2020, D.2008, D.2001;
   [...]

<L5>:;
D.2033 = (int) (signed short) ivtmp.67;
D.2035 = (long int) RealBitRevData[D.2033];
D.2038 = (long int) ImagBitRevData[D.2033];
tRealData = WReal * D.2035 + WImag * D.2038;
tImagData = WReal * D.2038 - WImag * D.2035;
D.2001 = (int) i;
D.2043 = (short int) (tRealData >> 15);
RealBitRevData[D.2033] = RealBitRevData[D.2001] - D.2043;
D.2046 = (short int) (tImagData >> 15);
ImagBitRevData[D.2033] = ImagBitRevData[D.2001] - D.2046;
RealBitRevData[D.2001] = D.2043 + RealBitRevData[D.2001];
ImagBitRevData[D.2001] = D.2046 + ImagBitRevData[D.2001];
i = (signed short) ((short unsigned int) i + ivtmp.78);
ivtmp.68 = ivtmp.68 + ivtmp.78;
ivtmp.67 = ivtmp.67 + ivtmp.78;
if (DataSize > (signed short) (ivtmp.68 - ivtmp.78)) goto <L5>; else goto <L7>;



The net result of these induction variables, and especially the type translations necessary to go between signed and unsigned and shorts and ints was an inner loop consisting of 42 instructions, as opposed to an inner loop of 32 instructions as produced by the gcc 3.4 compiler.


Cheers
  Nick


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]