importance of -fno-strength-reduce

importance of -fno-strength-reduce

Post by Bill Davidso » Sat, 14 Jun 1997 04:00:00



Hi:

I have noticed that the kernel Makefiles specify a compiler flag
"-fno-strength-reduce".  It is my understanding that this is because of
a bug in gcc < 2.7.2.[12] on the ix86 architecture.  It is also my
understanding that gcc-2.7.2.[12] has fixed this bug.  I use
gcc-2.7.2.2, and I successfully compiled and ran a small program that
purported to detect the strength-reduce bug.  However, I have no idea
what "strength-reduction" is, or what the bug is/was, or how to detect
it.

So my questions are:
1) Can I, using gcc-2.7.2.2, eliminate the -fno-strength-reduce flag for
kernel compiles?
2) Would it make any difference?
3) If I did eliminate that compiler option, how would I know that it was
a problem?  How would I know that it made a difference if it wasn't
catastrophic?

Thanks for your help/opinions.
--
+---------------------------------------+
|    Bill Davidson                      |

|    http://www.isisnet.com/bdavidson/  |
+---------------------------------------+

 
 
 

importance of -fno-strength-reduce

Post by Joe Bu » Sat, 14 Jun 1997 04:00:00



>I have noticed that the kernel Makefiles specify a compiler flag
>"-fno-strength-reduce".  It is my understanding that this is because of
>a bug in gcc < 2.7.2.[12] on the ix86 architecture.  It is also my
>understanding that gcc-2.7.2.[12] has fixed this bug.  I use
>gcc-2.7.2.2, and I successfully compiled and ran a small program that
>purported to detect the strength-reduce bug.  However, I have no idea
>what "strength-reduction" is, or what the bug is/was, or how to detect
>it.

Strength reduction is a loop optimization, replacing an expensive
operation (like multiplication) by a cheaper one (like addition).
For example:

double sum_every_nth_element(double* array, int length, int n, int offset) {
        double sum = 0.0;
        for (i = 0; i < length/n; i++) {
                sum += array[n*i+offset];
        }
        return sum;

Quote:}

Strength reduction can turn the n*i+offset into an addition of n to i
each time around the loop, as if you had written

        for (i = offset; i < length; i += n) {
                sum += array[i];
        }

Actually, it's a bit better than this: strength reduction can also
eliminate the implicit multiply-by-8 (shift left by 3) associated
with the array-of-double access.  What's going on at the machine level is
then

        register char* address = (char*)array + sizeof(double)*offset;
        register char* end = (char*)array + sizeof(double)*length;
        register int inc = sizeof(double)*n;
        for (; address < end; address += inc)
                // fetch a double from the address
                register e = *(double*)address;
                sum += e;
        }
        return sum;

If you say -fno-strength-reduce you are slowing down every traversal of an
array that isn't of type char.

In general, strength reduction involves finding "induction variables".  To
quote the comments in gcc's loop.c file:

  A "basic induction variable" or biv is a pseudo reg [for example, a
  variable or common sub-expression] that is set (within this loop) only by
  incrementing or decrementing it.  A "general induction variable" or giv is
  a pseudo reg whose value is a linear function of a biv.

In principle, you can eliminate all but one biv, and compute the giv's
more easily from the loop count that remains.  This may or may not be
worth it.

There was a bug in gcc which showed up only on Intel platforms, involving
some mixtures of signed and unsigned integers, which caused a bug.  In
practice the conditions to trigger the bug rarely occurred, but the Linux
kernel did trigger the bug.  gcc was making an incorrect optimization.

Quote:>So my questions are:
>1) Can I, using gcc-2.7.2.2, eliminate the -fno-strength-reduce flag for
>kernel compiles?

Yes.  This is why the FSF put out the release.

Quote:>2) Would it make any difference?

Your kernel will run a bit faster.

Quote:>3) If I did eliminate that compiler option, how would I know that it was
>a problem?  How would I know that it made a difference if it wasn't
>catastrophic?

It's always possible that a problem will arise in a kernel for some
reason, but I haven't seen any claims that the gcc team failed in what
they set out to do: eliminate the problem with strength reduction.

--
-- Joe Buck     http://www.synopsys.com/pubs/research/people/jbuck.html

Help stamp out Internet spam: see http://spam.abuse.net/spam/

 
 
 

importance of -fno-strength-reduce

Post by ro » Sat, 14 Jun 1997 04:00:00



        another dimension with:
 >
 >So my questions are:
 >1) Can I, using gcc-2.7.2.2, eliminate the -fno-strength-reduce flag for
 >kernel compiles?
 >2) Would it make any difference?
 >3) If I did eliminate that compiler option, how would I know that it was
 >a problem?  How would I know that it made a difference if it wasn't
 >catastrophic?
 >
        I would like to know the outcome on this as well, as I took
        statements about this being fixed, literally. I can say that at
        this point, it's at least not a catastrophic problem, since I've
        been running innd, compiled without the -fno-strength-reduce
        switch for a number of months with one uptime of 47 days and
        only a single crash from a bad inode on some md configured SCSI's.

drs
--
Will provide security scan of your network in
exchange for junk mail. Thorough scans for as
little a one parcel. Results available for a
nominal fee. Visa and MC accepted.

 
 
 

importance of -fno-strength-reduce

Post by Greg Walk » Sun, 15 Jun 1997 04:00:00



    >> So my questions are: 1) Can I, using
    >> gcc-2.7.2.2, eliminate the
    >> -fno-strength-reduce flag for kernel
    >> compiles?  2) Would it make any difference?

    Joe> Your kernel will run a bit faster.

Also the code size grows a little bit. Using
gcc-2.7.2.1, my 2.0.29 kernel went from 299505
bytes w/ the -fno-strength-reduce flag to 300050
bytes w/o it.  It still uses the same number of
mem pages, though; so it turns to not be a real
issue.  It would be nice if the strength-reduce
optimizations would also shrink code size, but
getting faster code is a good tradeoff I suppose.

Greg
--
Greg Walker

 
 
 

importance of -fno-strength-reduce

Post by Jan Echterna » Tue, 17 Jun 1997 04:00:00




Quote:> There was a bug in gcc which showed up only on Intel platforms, involving
> some mixtures of signed and unsigned integers, which caused a bug.  In
> practice the conditions to trigger the bug rarely occurred, but the Linux
> kernel did trigger the bug.  gcc was making an incorrect optimization.

Only a small correction:  A mixture of signed and unsigned did interfere
with the bug, but did not cause it.  The bug could be reproduced with
only signed, or only unsigned integers.

The bug was that gcc optimized a loop of the form

  for (i = start; i < end; i++)
    ...x = i + offset;...

to

  for (i = start + offset; i < end + offset; i++)
    ...x = i;...

which is generally not correct.

--
Jan

 
 
 

importance of -fno-strength-reduce

Post by Joe Bu » Tue, 17 Jun 1997 04:00:00



>The bug was that gcc optimized a loop of the form

>  for (i = start; i < end; i++)
>    ...x = i + offset;...

>to

>  for (i = start + offset; i < end + offset; i++)
>    ...x = i;...

>which is generally not correct.

No, the bug is not that gcc does this optimization, which is often
correct and is a standard transformation done by decent compilers for
the last 20 years; it is that the code that is supposed to check that the
optimization is correct gave a wrong answer.  (All the distributed
test cases showing the bug built correctly on Sparc platformes, so
it seemed to either be Intel-specific or at least to be triggered
much more often on Intel platforms).

--
-- Joe Buck     http://www.synopsys.com/pubs/research/people/jbuck.html

Help stamp out Internet spam: see http://spam.abuse.net/spam/

 
 
 

importance of -fno-strength-reduce

Post by Mike Meissne » Tue, 17 Jun 1997 04:00:00



> If you say -fno-strength-reduce you are slowing down every traversal of an
> array that isn't of type char.

Except on the x86, it adds to the register pressure, which means something else
may get tossed to the stack instead of living in registers.  Also, I recall,
the 88k dhrystone actually slowed down by strength-reduction (strength
reduction at the time [7 years ago] did not take into account that the machine
could fold the shift operation into the address mode).

Quote:> In general, strength reduction involves finding "induction variables".  To
> quote the comments in gcc's loop.c file:

>   A "basic induction variable" or biv is a pseudo reg [for example, a
>   variable or common sub-expression] that is set (within this loop) only by
>   incrementing or decrementing it.  A "general induction variable" or giv is
>   a pseudo reg whose value is a linear function of a biv.

> In principle, you can eliminate all but one biv, and compute the giv's
> more easily from the loop count that remains.  This may or may not be
> worth it.

> There was a bug in gcc which showed up only on Intel platforms, involving
> some mixtures of signed and unsigned integers, which caused a bug.  In
> practice the conditions to trigger the bug rarely occurred, but the Linux
> kernel did trigger the bug.  gcc was making an incorrect optimization.

It was most prominant on the x86 platform (since it caused a Linux device
driver to be miscompiled, but it did show up rarely on the PowerPC).

--
Michael Meissner, Cygnus Solutions (East Coast)
4th floor, 955 Massachusetts Avenue, Cambridge, MA 02139, USA

 
 
 

1. Q:Kernel compiled with no -fno-strength-reduce??

I've recently installed the gcc-272-no-sr-bug-fix distribution (which I gather
is the compiler with the bug fix for the strength-reduce bug that's plagued
previous releases) and compiled the latest kernel without the -fno-strength-reduce.

My question is:

 * if the gcc-272-no-sr-bug-fix release has the strength-reduce problem
   fixed, and the kernel is 20k smaller (!) than compared to 1.3.100 compiled with
   -fno-strength-reduce [with same hardware configs + optimization flags], and
    seems to run 5-10% faster,

 why retain the `-fno-strength-reduce' flag?

Cheers,
--
                     _______.+= From Martin Glanvill =+._______
                    /  __    i486-DX4 100 Linux 1.99.7        /\
                   /  / /\    __   .___   __  __   __  __    / /
                  /  / /_/_  / /\ / .. \ / /_/ /\ / / / /\  / /
                 /  /_____/\/_/ //_/ /_/\*___.` /.`.+`_` ` / /
                /   \_____\/\_\/ \_\/\_\/\___\.` \_\/\_\/ / /
               /__/ Maths Dept, University of Waikato /__/ /
               \__\/ Private Bag 3105, Hamilton, N.Z. \__\/

2. fonts

3. gcc 2.7.2 & -fno-strength-reduce bug?

4. Unable to telnet

5. Don't compile egcs-1.1.2 itself (gcc-2.91.66, kgcc on RedHat) , with -fno-strength-reduce

6. linux <-parallel cable-> win95 ?

7. gcc 2.7.2.1 & strength reduce bug?

8. What Linux bubble burst?

9. Strength reduce bug - has it been fixed?

10. strength-reduce and GCC

11. Wine is affected by the reduce-strength-bug

12. GCC 2.7.2 strength-reduce how serious is it ??

13. Strength reduce bug - has it been fixed?