[cfe-dev] [RFC] Introduce overflow builtins

[Xi Wang]

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