llvm dev - Mar 2019 - enable optimization of integer multiplication and modulo using faster operations?

Hi,

$ clang -Wall -pedantic -O3 -S -emit-llvm -c -o - main.c

When I compile the following .c file using the above clang command, I
still get mul in the IR code. But isn't that 31 is just 32 - 1, so
that the implementation can use left shift by 4 and subtract the
original number?

#include <stdio.h>
int f(int x) {
    return x * 31;
}
int main() {
    int x=1;
    printf("%d\n", f(x));
    return 0;
}

; Function Attrs: norecurse nounwind readnone ssp uwtable
define i32 @f(i32) local_unnamed_addr #0 {
  %2 = mul nsw i32 %0, 31
  ret i32 %2
}

Also, I see this comment. But % is just translated to `srem` by clang.

"Turns out if you do a modulo by a constant, the compiler knows a
bunch of tricks to make this fast."
https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/

Is clang able to produce optimized code for integer multiplication and
modulo operations? Thanks.

-- 
Regards,
Peng

Most of the optimizations for these things are handled after IR in
SelectionDAG often with target specific knowledge. For IR we want to
preserve the simplest operation as long as possible to make sure
optimization passes can reason about it.

~Craig


On Tue, Mar 5, 2019 at 8:35 PM Peng Yu via llvm-dev <llvm-dev at
lists.llvm.org>
wrote:
> Hi,
>
> $ clang -Wall -pedantic -O3 -S -emit-llvm -c -o - main.c
>
> When I compile the following .c file using the above clang command, I
> still get mul in the IR code. But isn't that 31 is just 32 - 1, so
> that the implementation can use left shift by 4 and subtract the
> original number?
>
> #include <stdio.h>
> int f(int x) {
>     return x * 31;
> }
> int main() {
>     int x=1;
>     printf("%d\n", f(x));
>     return 0;
> }
>
> ; Function Attrs: norecurse nounwind readnone ssp uwtable
> define i32 @f(i32) local_unnamed_addr #0 {
>   %2 = mul nsw i32 %0, 31
>   ret i32 %2
> }
>
> Also, I see this comment. But % is just translated to `srem` by clang.
>
> "Turns out if you do a modulo by a constant, the compiler knows a
> bunch of tricks to make this fast."
> https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/
>
> Is clang able to produce optimized code for integer multiplication and
> modulo operations? Thanks.
>
> --
> Regards,
> Peng
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190305/efebe89f/attachment.html>

> On Mar 5, 2019, at 23:34, Peng Yu via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Is clang able to produce optimized code for integer multiplication and
> modulo operations? Thanks.
It certainly seems to, just not in IR as Craig mentioned. I put your function
into compiler explorer and you can see it was compiled to a left shift by 5 and
a subtraction, just as you'd expect <https://godbolt.org/z/f4gRId>.

-- 
Stephen Checkoway