4

I am contemplating a fixed-point arithmetic library, and in order to decide on how much optimization should be done by the library itself (through expression templates) I started questioning how much will already be done by the optimizer. Take the following example for instance:

//This is a totally useless function to exemplify my point
void Compare(FixedPoint a, FixedPoint b) {
   if(a/b>10) {
      ... do stuff
   }
}

Now, in this function, a typical implementation of the FixedPoint class will cause

if( ( (a_<<N) / b_) > (10 <<N) ) {
... do stuff
}

Where N is the number of fractional bits. That expression could mathematically be transformed into:

(a_ > 10*b_)

even though this transformation will not result in the same behavior when you consider integer overflow. The users of my library will presumably care about the mathematical equivalence and would rather have the reduced version (possibly provided through expression templates).

Now, the question is: Will the optimizer dare do the optimization itself, even though the behavior is not strictly the same? Should I bother with such optimizations? Note that such optimizations aren't trivial. In reality, you rarely have to do any bit shifts when you're using fixed-point arithmetic if you actually do these optimizations.

enobayram
  • 4,650
  • 23
  • 36
  • 4
    Simple rule: If the compiler can't prove to itself that the behavior won't change then it won't optimize. – P.P Oct 15 '12 at 09:24
  • Furthermore, you already came up of an example of where it won't match. (overflow) That by itself will already forbid the compiler from doing this optimization. That said, the compiler may do other tricks (such as promoting to a larger type). But a quick test shows that VS2010 does not do this optimization. – Mysticial Oct 15 '12 at 09:28
  • @Mystical doesn't the c standard except the programmer to avoid overflows, and thus allows for optimisations disregarding overflows. (I think there was a question here on SO were a loop would not terminate, since the termination condition relied on an overflow (somthing with `for(int i=0;i>=0;i++);` if I recall corectly). However I am ot entirely sure about this. – ted Oct 15 '12 at 09:40
  • @ted What a coincidence! [That question](http://stackoverflow.com/questions/7682477/gcc-fail-or-undefined-behavior) you're referring to was asked by me. :) In this case, doing the optimization will *introduce* overflows if `10*b_` goes over. So even if `a/b` doesn't overflow, `10*b_` could. So the compiler can't do it without promoting to a larger type. – Mysticial Oct 15 '12 at 09:42
  • @Mystical: thank you, lucky me now I learned even more from your question. – ted Oct 15 '12 at 09:47

1 Answers1

1

That will depend on whether the a_ and b_ types are signed or unsigned.

In C and C++ signed overflow is technically undefined behavior, while unsigned overflow is done using two-complement arithmetic.

Nevertheless, some compilers refuse to optimize the that code because many programs rely on the two-complement behavior of the signed overflow.

Good modern compilers will have an option to enable/disable this particular assumption: that signed integers won't overflow. What option is the default will vary with the compiler.

With GCC, for example, see options -fstrict-overflow/-fno-strict-overflow and the related warning -Wstrict-overflow.

rodrigo
  • 94,151
  • 12
  • 143
  • 190
  • Thank you for your answer, I guess I'm better off doing such optimizations through expression templates then. – enobayram Oct 15 '12 at 10:36
  • It also depends upon whether they are larger or smaller than `int`. Unsigned values smaller than `int` get promoted to signed values regardless of context, which can cause Undefined Behavior even in cases where the upper bits of a computation could never have any defined effect on the result. – supercat May 21 '15 at 22:50