llvm dev - Aug 2012 - [LLVMdev] 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

On Wed, Aug 22, 2012 at 2:00 PM, Xi Wang <xi.wang at gmail.com>
wrote:
> 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?
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