[InstCombine] `x * 3 / 2` => `x + x / 2` when overflow is impossible
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
[Compiler explorer](https://godbolt.org/z/dsPsbr4GP)
[Alive proof](https://alive2.llvm.org/ce/z/qqbAQ5)
InstCombine performs this rewrite for unsigned integers, but not for signed integers:
```c++
#include
extern "C" {
auto src1(uint32_t x) -> uint32_t {
uint32_t product;
if (__builtin_mul_overflow(x, 3, &product)) __builtin_unreachable();
return product / 2;
}
auto tgt1(uint32_t x) -> uint32_t { return x + (x / 2); }
auto src2(int32_t x) -> int32_t {
int32_t product;
if (__builtin_mul_overflow(x, 3, &product)) __builtin_unreachable();
return product / 2;
}
auto tgt2(int32_t x) -> int32_t { return x + (x / 2); }
}
```
```llvm
define dso_local range(i32 0, -2147483648) i32 @src1(i32 noundef %x) local_unnamed_addr {
entry:
%0 = lshr i32 %x, 1
%div1 = add nuw i32 %0, %x
ret i32 %div1
}
define dso_local noundef i32 @tgt1(i32 noundef %x) local_unnamed_addr {
entry:
%div2 = lshr i32 %x, 1
%add = add i32 %div2, %x
ret i32 %add
}
define dso_local range(i32 -1073741824, 1073741824) i32 @src2(i32 noundef %x) local_unnamed_addr {
entry:
%0 = mul nsw i32 %x, 3
%div = sdiv i32 %0, 2
ret i32 %div
}
define dso_local i32 @tgt2(i32 noundef %x) local_unnamed_addr {
entry:
%div = sdiv i32 %x, 2
%add = add nsw i32 %div, %x
ret i32 %add
}
```
On AArch64 and RISC-V this saves one instruction:
```asm
src1:
add w0, w0, w0, lsr #1
ret
tgt1:
add w0, w0, w0, lsr #1
ret
src2:
add w8, w0, w0, lsl #1
add w8, w8, w8, lsr #31
asr w0, w8, #1
ret
tgt2:
add w8, w0, w0, lsr #31
add w0, w0, w8, asr #1
ret
```
```asm
src1:
srliw a1, a0, 1
addw a0, a0, a1
ret
tgt1:
srliw a1, a0, 1
addw a0, a0, a1
ret
src2:
slli a1, a0, 1
add a0, a0, a1
srliw a1, a0, 31
add a0, a0, a1
sraiw a0, a0, 1
ret
tgt2:
srliw a1, a0, 31
add a1, a1, a0
sraiw a1, a1, 1
addw a0, a0, a1
ret
```
Contributor guide
Assessment
This issue has not been assessed yet.