llvm / llvm/llvm-project

Missed optimization: fold shl (sdiv X, C), log2(C) to and X, -C when X is provably non-negative

Open
#186,517 2 comments 0 reactions 1 assignee Claimed by @Camsyn View on GitHub
llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

```llvm
define i64 @src(i64 %arg0, i64 %arg1, ptr %arg2) {
%v0 = getelementptr inbounds i8, ptr %arg2, i64 %arg1
%v1 = sub nsw i64 2, %arg0
%v2 = getelementptr inbounds nuw float, ptr %v0, i64 %arg0
%v3 = ptrtoint ptr %v2 to i64
%v4 = lshr exact i64 %v3, 2
%v5 = sub nsw i64 0, %v4
%v6 = and i64 %v5, 3
%v7 = call i64 @llvm.smin.i64(i64 %v6, i64 %v1)
%v8 = sub nsw i64 %v1, %v7
%v9 = sdiv i64 %v8, 4
%v10 = shl nsw i64 %v9, 2
%v11 = add i64 %v10, %v7
ret i64 %v11
}

define i64 @tgt(i64 %arg0, i64 %arg1, ptr %arg2) {
%v0 = getelementptr inbounds i8, ptr %arg2, i64 %arg1
%v2 = getelementptr inbounds nuw float, ptr %v0, i64 %arg0
%v3 = ptrtoint ptr %v2 to i64
%v4 = lshr exact i64 %v3, 2
%v5 = sub nsw i64 0, %v4
%v6 = and i64 %v5, 3
%v1 = sub nsw i64 2, %arg0
%v7 = call i64 @llvm.smin.i64(i64 %v6, i64 %v1)
%v8 = sub nsw i64 %v1, %v7
%v10 = and i64 %v8, -4
%v11 = add i64 %v10, %v7
ret i64 %v11
}
```
available in alive2 when time limit = 50000
```
define i64 @src(i64 %lpo_arg0, i64 %lpo_arg1, ptr %lpo_arg2) {
#0:
%v0 = gep inbounds ptr %lpo_arg2, 1 x i64 %lpo_arg1
%v1 = sub nsw i64 2, %lpo_arg0
%v2 = gep inbounds nuw ptr %v0, 4 x i64 %lpo_arg0
%v3 = ptrtoint ptr %v2 to i64
%v4 = lshr exact i64 %v3, 2
%v5 = sub nsw i64 0, %v4
%v6 = and i64 %v5, 3
%v7 = smin i64 %v6, %v1
%v8 = sub nsw i64 %v1, %v7
%v9 = sdiv i64 %v8, 4
%v10 = shl nsw i64 %v9, 2
%v11 = add i64 %v10, %v7
ret i64 %v11
}
=>
define i64 @tgt(i64 %lpo_arg0, i64 %lpo_arg1, ptr %lpo_arg2) {
#0:
%v0 = gep inbounds ptr %lpo_arg2, 1 x i64 %lpo_arg1
%v2 = gep inbounds nuw ptr %v0, 4 x i64 %lpo_arg0
%v3 = ptrtoint ptr %v2 to i64
%v4 = lshr exact i64 %v3, 2
%v5 = sub nsw i64 0, %v4
%v6 = and i64 %v5, 3
%v1 = sub nsw i64 2, %lpo_arg0
%v7 = smin i64 %v6, %v1
%v8 = sub nsw i64 %v1, %v7
%v10 = and i64 %v8, -4
%v11 = add i64 %v10, %v7
ret i64 %v11
}
Transformation seems to be correct!
```
godbolt: https://godbolt.org/z/axfTd64jj

Pattern found in: https://github.com/dtcxzyw/llvm-opt-benchmark/blob/main/bench/g2o/optimized/vertex_ellipse.ll

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.