llvm / llvm/llvm-project

[InstCombine] `x * 3 / 2` => `x + x / 2` when overflow is impossible

Open
#209,929 5 comments 0 reactions 1 assignee Claimed by @iamaayushrivastava View on GitHub
llvm:instcombine missed-optimization
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.