RFC: optimizing integer overflow checks

Hi,

Integer overflow checks often use divisions, which may hurt performance. See also

  http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48580

Here's a prototype implementation of two passes that complement -instcombine. They recognize common checking patterns and rewrite them using overflow intrinsics.

  https://gist.github.com/3429064
  https://gist.github.com/3429069

Here goes an example.

$ cat t.c

#include <stdlib.h>
#include <stdint.h>

void *malloc_array_1(size_t n, size_t size)
{
        if (size && n > SIZE_MAX / size)
                return NULL;
        return malloc(n * size);
}

void *malloc_array_2(size_t n, size_t size)
{
        size_t bytes = n * size;
        if (size && n != bytes / size)
                return NULL;
        return malloc(bytes);
}

$ clang -emit-llvm -S -o - t.c | opt -S -mem2reg -simplifycfg -overflow-idiom -simplifycfg -sink -overflow-combine -adce

define i8* @malloc_array_1(i64 %n, i64 %size) nounwind uwtable ssp {
entry:
  %0 = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %n, i64 %size)
  %cmp = extractvalue { i64, i1 } %0, 1
  br i1 %cmp, label %return, label %if.end

if.end: ; preds = %entry
  %mul = extractvalue { i64, i1 } %0, 0
  %call = call i8* @malloc(i64 %mul)
  br label %return

return: ; preds = %entry, %if.end
  %retval.0 = phi i8* [ %call, %if.end ], [ null, %entry ]
  ret i8* %retval.0
}

define i8* @malloc_array_2(i64 %n, i64 %size) nounwind uwtable ssp {
entry:
  %0 = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %n, i64 %size)
  %cmp = extractvalue { i64, i1 } %0, 1
  br i1 %cmp, label %return, label %if.end

if.end: ; preds = %entry
  %mul = extractvalue { i64, i1 } %0, 0
  %call = call i8* @malloc(i64 %mul)
  br label %return

return: ; preds = %entry, %if.end
  %retval.0 = phi i8* [ %call, %if.end ], [ null, %entry ]
  ret i8* %retval.0
}

Any comments?

- xi

If you're proposing this for mainline, please don't use separate
passes; converting comparisons to overflow intrinsics should be done
by instcombine, and redundant operations should be eliminated by GVN.

-Eli