llvm / llvm/llvm-project

`(x + y) / 2` does not become `(x + y) >> 1` when `x` and `y` are both positive.

Open
#212,382 1 comment 0 reactions 1 assignee Claimed by @VachanVY View on GitHub
llvm:analysis missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

This code computes the average of `x` and `y`. `x` and `y` are both assumed to be positive, and the result of `x + y` is assumed to have no signed overflow (NSW).
```c
int test1(int x, int y) {
if (x < 0 || y < 0) {
__builtin_unreachable();
}
return (x + y) / 2;
}
```
Since the result of `x + y` is positive (NSW), `(x + y) / 2` can be converted into `(x + y) >> 1`. However, this transformation is sometimes missed:
```
if (x < 0 || y < 0) __builtin_unreachable() // Missed (remains as sdiv)
if (x < 0 || y <= 0) __builtin_unreachable() // Okay (becomes lshr)
if (x <= 0 || y < 0) __builtin_unreachable() // Okay (becomes lshr)
if (x <= 0 || y <= 0) __builtin_unreachable() // Okay (becomes lshr)
```
https://godbolt.org/z/qKxdcvEbM

A similar thing happens if there are more than two arguments:
https://godbolt.org/z/xdvGad9hW

From some brief testing, it looks like Clang 13.0.0 and Clang 13.0.1 were able to correctly apply the optimization (for both 2 and 3 arguments), whereas Clang 12.0.1 and Clang 14.0.0 do not.

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.