On Jul 30, 2014, at 16:39 Geert Bosch <bos...@mac.com> wrote: > On Jul 23, 2014, at 10:56 AM, Thomas Mertes <thomas.mer...@gmx.at> wrote: > > > One such feature is the detection of signed integer overflow. It is > > not hard, to detect signed integer overflow with a generated C > > program, but the performance is certainly not optimal. Signed integer > > overflow is undefined behavior in C and the access to some overflow > > flag of the CPU is machine dependent. > > Actually, doing proper signed integer overflow checking in a front end > can be surprisingly cheap. > > I have some experience with this for the Ada front end, and found the > following: > - In many cases it may be cheapest to widen computations to avoid > overflow, and/or check it less frequently.
Do you do a dataflow analysis to avoid some overflow checks? Seed7 supports only 64-bit signed integers. I am using 128-bit arithmetic, when multiplying two values that are not known at compile-time. In this case I multiply with 128-bit and check for overflow afterwards. The the 128-bit product is checked for an overflow with: (__int128_t) (int64_t) (product) != (product) But maybe the simple check below is better: product < -9223372036854775808 && product > 9223372036854775807 Is it possible to decide that without performance measurements? Until now I have avoided performance measurements for the target C compiler. Not all compilers support 128-bit arithmetic. For this case it is necessary to do a division to get a bound for the overflow check. When multiplying two values that are not known at compile-time and without 128-bit arithmetic I use (a and b are factors, l = -9223372036854775808, u = 9223372036854775807): a<0&&(b<0&&a<u/b||b>0&&a<l/b) || a>0&&(b<0&&b<l/a||b>0&&b>u/a) Note that for the non-overflow case a division is done at runtime: Either u/b, l/b, l/a or u/a must be computed. Maybe you have an idea how to avoid the division. > - Even if you need to check, often one side is known to be constant, > in which case a simple comparison of the input argument is sufficient For addition and subtraction I also do just one comparison, when one argument is constant. When one side of a multiplication is known to be constant I still have to check, if the other argument is within a range. My range check for this was (l=lower bound, u=upper bound): x<l||x>u Recently I discoved this (it works only for twos-complement): (unsigned)x-l>(unsigned)u-l A quick measurement did not show a speedup. Maybe you have more knowledge. Another posibility is: x<l|x>u This would avoid a jump. Until now I have not measured it. What would you suggest? > - In other cases, the sign of one of the operands is known, > simplifying the check > - Conversions from signed to unsigned types is essentially free and > well-defined, so do the overflow check using unsigned types, but use > signed integer operations for the actual computation: Do you do the computation twice, once for the check and again for the actual computation? When a and b are not known at compile time I use the following strategy for a += b. The addition is done with unsigned arithmetic c=(int64_t)((uint64_t)a+(uint64_t )b) and the overflow check is done with b>0&&c<a || b<0&&c>a Finally the result is assigned to a with a=c When a and b are not known at compile time I use the following strategy for a + b. The check for overflow is done with b<0&&a<INT64_MIN-b || b>=0&&a>INT64_MAX-b Is the unsigned strategy better here? Do you know about a simpler check? Using 128-bit arithmetic was slower than the check above. > - By using a simple comparison to jump to a no_return function, GCC > knows the condition is expected to be false and will optimize accordingly My function to raise an exception is a no_return function. For the exception conditions I use __builtin_expect to specify that an exception is unlikely. > Note that in the second case above, the extra conditional (which will almost > always be correctly predicted by the CPU and often is free) will, combined > with > the conditional transfer of control to a no_return routine, in effect > provide range information to the compiler, allowing the elimination of > redundant checks etc. The positive effects of expanding checks to optimizable > C-like constructs are far larger than the eventual instruction selection. > We found the cost of overflow, even without "jo" instructions being generated, > to be generally in the order of 1 - 2% in execution speed and a bit more in > growth of executable size (in our case around 10% due to generating > exceptions with > location information). In the moment I need more than 1 - 2% to do the overflow checking. Maybe you have ideas how I could improve this. I expected that a compiler frontend has more possibilities than C. > If you make overflow checking "special" early by resorting specific builtins, > -ftrapv or similar, you'll lose out in the general purpose optimization > passes and in > my experience will get far worse code. If your language semantics are: > provide the > numerically correct answer (as if computed with unbounded range) or raise an > exception, you can probably do better by using wider types and smart > expansions > to avoid overflow while retaining C-level intermediate code. Since I use 64-bit signed integers the possibility to use wider types is limited. > Anyway, the Ada front end is proof that efficient overflow checking is > possible > without any special support in the back end. Thank you very much. Hopefully you can help me to do a smarter overflow checking. See my questions above. Greetings Thomas Mertes -- Seed7 Homepage: http://seed7.sourceforge.net Seed7 - The extensible programming language: User defined statements and operators, abstract data types, templates without special syntax, OO with interfaces and multiple dispatch, statically typed, interpreted or compiled, portable, runs under linux/unix/windows.