This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: C as intermediate language, signed integer overflow and -ftrapv


On Jul 23, 2014, at 10:56 AM, Thomas Mertes <thomas.mertes@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

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]