1

Consider the following piece of code showing some simple arithmetic operations

    int result = 0;

    result = c * (a + b) + d * (a + b) + e;

To get the result in the expression above the cpu would need to execute two integer multiplications and three integer additions. However algebraically the above expression could be simplified to the code below.

 result = (c + d) * (a + b) + e

The two expressions are algebraically identical however the second expression only contains one multiplication and three additions. Is gcc (or other compilers for that matter) able to make this simple optimization on their own.

Now assuming that the compiler is intelligent enough to make this simple optimization, would it be able to optimize something more complex such as the Trapezoidal rule (used for numerical integration). Example below approximates the area under sin(x) where 0 <= x <= pi with a step size of pi/4 (small for the sake of simplicity). Please assume all literals are runtime variables.

#include <math.h>

// Please assume all literals are runtime variables. Have done it this way to 
// simplify the code.
double integral = 0.5 * ((sin(0) + sin(M_PI/4) * (M_PI/4 - 0) + (sin(M_PI/4) + 
    sin(M_PI/2)) * (M_PI/2 - M_PI/4) + (sin(M_PI/2) + sin(3 * M_PI/4)) * 
    (3 * M_PI/4 - M_PI/2) + (sin(3 * M_PI/4) + sin(M_PI)) * (M_PI - 3 * M_PI/4));

Now the above function could be written like this once simplified using the trapezoidal rule. This drastically reduces the number of multiplications/divisions needed to get the same answer.

integral = 0.5 * (1 / no_steps /* 4 in th case above*/) * 
    (M_PI - 0 /* Upper and lower limit*/) * (sin(0) + 2 * (sin(M_PI/4) +
    sin(3 * M_PI/4)) + sin(M_PI));
silvergasp
  • 1,517
  • 12
  • 23
  • 1
    Please provide a link to the specification of the language C/C++. Until then there are only the two **different** languages C and C++. Pick one! And your question is too broad for SO. Please do some research yourself. The gcc mailing list might be a good start. Or you just read the source code. – too honest for this site Jan 19 '16 at 15:01
  • 1
    You could always compile and check the assembly to see what it does. – NathanOliver Jan 19 '16 at 15:01
  • 1
    Beware! This sort of algebraic rearrangement often breaks when you start to consider integer overflow. I can't think of counter examples for this particular expression, but there are plenty of expressions where it will break. – Martin Bonner supports Monica Jan 19 '16 at 15:09
  • Your second example (with floating point) is much less likely to be optimized. Floating point arithmetic does *not* obey the algebraic identities like `(a-b)*c` == `a*c - b*c` - underflow causes all sorts of strange behaviour. – Martin Bonner supports Monica Jan 19 '16 at 15:13
  • [Similar question](http://stackoverflow.com/questions/32696860/clang-reciprocal-to-1-optimisations). – Lundin Jan 19 '16 at 16:06
  • The standard says C++ evaluates expressions according to precedence and associativity. Most c++ compilers emit three multiplies for the expression result = 3 * i * 5 * 7; But when the optimizer gets ahold of this expression it becomes result = i * 105; I was taught (in the mid 90s) to put all the constant terms together if you wanted the optimized result, but now it doesn't seem necessary. Why does the optimizer get to do things the compiler explicitly doesn't do? – seattlecpp Jul 22 '20 at 23:31

2 Answers2

7

GCC (and most C++ compilers, for that matter) does not refactor algebraic expressions.

This is mainly because as far as GCC and general software arithmetic is concerned, the lines

double x = 0.5 * (4.6 + 6.7);
double y = 0.5 * 4.6 + 0.5 * 6.7;

assert(x == y); //Will probably fail!

Are not guaranteed to be evaluate to the exact same number. GCC can't optimize these structures without that kind of guarantee.

Furthermore, order of operations can matter a lot. For example:

int x = y;
int z = (y / 16) * 16;

assert(x == z); //Will only be true if y is a whole multiple of 16

Algebraically, those two lines should be equivalent, right? But if y is an int, what it will actually do is make x equal to "y rounded to the lower whole multiple of 16". Sometimes, that's intended behavior (Like if you're byte aligning). Other times, it's a bug. The important thing is, both are valid computer code and both can be useful depending on the circumstances, and if GCC optimized around those structures, it would prevent programmers from having agency over their code.

Xirema
  • 19,889
  • 4
  • 32
  • 68
  • On advice from nathan oliver I dissasembled the integer example above and it generates the exact same assembly. In that case gcc has made an optimisation by refactoring `result = c * (a + b) + d * (a + b) + e;` to `result = (c + d) * (a + b) + e;` or perhaps the other way around I don't know. You are right however about the floating point example. I do not understand assembly though so Couldn't work out what was happening there. – silvergasp Jan 19 '16 at 15:30
  • In the example 1, the compiler will simply hard-code the computed result, no run time computation is required. However, for non-constant values, it may optimize with `-ffast-math` enabled. 2. That example is not correct, because mathematical `/` is not the same as C++ `/`. Also, GCC does optimize that to a simple bitwise operation. – user202729 Jan 15 '20 at 05:34
1

Yes, optimizers, gcc's included, do optimizations of this type. Not necessarily the expression that you quoted exactly, or other arbitrarily complex expressions. But a simpler expresion, (a + a) - a is likely to be optimized to a for example. Another example of possible optimization is a*a*a*a to temp = a*a; (temp)*(temp)

Whether a given compiler optimizes the expressions that you quote, can be observed by reading the output assembly code.

No, this type of optimization is not used with floating points by default (unless maybe if the optimizer can prove that no accuracy is lost). See Are floating point operations in C associative? You can let for example gcc do this with -fassociative-math option. At your own peril.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • @user202729 Only signed integer overflow is undefined. Unsigned arithmetic is modular. I cannot remember what I was trying to say when I wrote the answer though. I'll remove the statement as it is misleading. – eerorika Jan 15 '20 at 05:44