[cfe-dev] [RFC] Introduce overflow builtins
Xi Wang
xi.wang at gmail.com
Sun Mar 18 23:03:34 PDT 2012
Hi,
Currently C/C++ programmers write ad-hoc integer overflow checks.
For example,
void *malloc_array(size_t n, size_t size)
{
if (size && n > SIZE_MAX / size)
return NULL;
return malloc(n * size);
}
Some programmers would write:
size_t bytes = n * size;
if (size && n != bytes / size)
return NULL;
Or in some crazier way:
https://github.com/ivmai/bdwgc/commit/83231d0ab5ed60015797c3d1ad9056295ac3b2bb
#define SQRT_SIZE_MAX ((1U << (sizeof(size_t) * 8 / 2)) - 1)
if ((size | n) > SQRT_SIZE_MAX /* fast test */
&& size && n > SIZE_MAX / size)
return NULL;
Downsides of ad-hoc overflow checks.
1) Hard to read.
2) Error-prone --- even true for overflow checking libraries written
by security experts (see http://blog.regehr.org/archives/593).
3) Performance. Below is the generated code of the first example.
Neither GCC nor Clang optimizes away the division (blame instcombine?).
malloc_array: # @malloc_array
.cfi_startproc
# BB#0: # %entry
testq %rsi, %rsi
je .LBB0_3
# BB#1: # %land.rhs
movq $-1, %rax
xorl %edx, %edx
divq %rsi
cmpq %rdi, %rax
jae .LBB0_3
# BB#2: # %return
xorl %eax, %eax
ret
.LBB0_3: # %if.end
imulq %rdi, %rsi
movq %rsi, %rdi
jmp malloc # TAILCALL
.Ltmp0:
.size malloc_array, .Ltmp0-malloc_array
.cfi_endproc
Let's consider adding overflow builtins to Clang, in the form:
bool __overflow_*(T*, T, T);
With overflow builtins, programmers can implement the example
as follows.
void *malloc_array(size_t n, size_t size)
{
size_t bytes;
if (__overflow_umul(&bytes, n, size))
return NULL;
return malloc(bytes);
}
These builtins can be easily lowered to LLVM overflow intrinsics
llvm.*.with.overflow.*. In the generated code, there is only one
more jno instruction.
malloc_array: # @malloc_array
.cfi_startproc
# BB#0: # %entry
movq %rdi, %rax
mulq %rsi
jno .LBB0_2
# BB#1: # %return
xorl %eax, %eax
ret
.LBB0_2: # %if.end
movq %rax, %rdi
jmp malloc # TAILCALL
.Ltmp0:
.size malloc_array, .Ltmp0-malloc_array
.cfi_endproc
The patch is available at:
https://github.com/xiw/clang/compare/xiw:master...xiw:builtin-overflow
Also see
http://llvm.org/bugs/show_bug.cgi?id=12290
- xi
More information about the cfe-dev
mailing list