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.
- 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
- 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:
- 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
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).
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.
Anyway, the Ada front end is proof that efficient overflow checking is possible
without any special support in the back end.
-Geert
