[LLVMdev] RFC: optimizing integer overflow checks

[Xi Wang]

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