[LLVMdev] RFC: optimizing integer overflow checks

Eli Friedman eli.friedman at gmail.com
Fri Aug 24 17:42:50 PDT 2012


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



More information about the llvm-dev mailing list