[InstCombine] Fold redundant zero check of inlined std::vector::_M_check_len result
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
I found a missed InstCombine fold in an inlined libstdc++ `std::vector::_M_check_len(1, ...)` growth path.
A reduced pattern is:
```llvm
declare i64 @llvm.umax.i64(i64, i64)
declare i64 @llvm.umin.i64(i64, i64)
define i1 @src_check_len_n1_ne_zero(i64 %size) {
; Models _M_check_len(1):
; len = overflow ? INTMAX : umin(size + umax(size, 1), INTMAX)
; Since umax(size, 1) is non-zero and overflow selects non-zero INTMAX,
; len is always non-zero.
%max = call i64 @llvm.umax.i64(i64 %size, i64 1)
%add = add i64 %max, %size
%ov = icmp ult i64 %add, %size
%min = call i64 @llvm.umin.i64(i64 %add, i64 9223372036854775807)
%len = select i1 %ov, i64 9223372036854775807, i64 %min
%r = icmp ne i64 %len, 0
ret i1 %r
}
define i1 @tgt_check_len_n1_ne_zero(i64 %size) {
ret i1 true
}
```
The corresponding eq 0 form can be folded to false:
```llvm
declare i64 @llvm.umax.i64(i64, i64)
declare i64 @llvm.umin.i64(i64, i64)
define i1 @src_check_len_n1_eq_zero(i64 %size) {
%max = call i64 @llvm.umax.i64(i64 %size, i64 1)
%add = add i64 %max, %size
%ov = icmp ult i64 %add, %size
%min = call i64 @llvm.umin.i64(i64 %add, i64 9223372036854775807)
%len = select i1 %ov, i64 9223372036854775807, i64 %min
%r = icmp eq i64 %len, 0
ret i1 %r
}
define i1 @tgt_check_len_n1_eq_zero(i64 %size) {
ret i1 false
}
```
This pattern appears in optimized IR generated from a vector growth path. In the real code, %len may still be used as the allocation size, so the goal is not necessarily to remove the %len computation itself. The useful fold is to remove the redundant zero check:
```llvm
%len = select i1 %ov, i64 INTMAX, i64 %min
%iszero = icmp eq i64 %len, 0
```
For _M_check_len(1, ...), %len cannot be zero.
### Reasoning:
If the overflow arm is selected, the result is INTMAX, which is non-zero.
Otherwise the result is umin(%add, INTMAX).
Since INTMAX is non-zero, this can be zero only if %add == 0.
%add = %size + umax(%size, 1).
With no unsigned overflow selected, %add == 0 would imply %size == 0.
But if %size == 0, then umax(%size, 1) == 1, so %add == 1.
Therefore %len is always non-zero.
One implementation detail to be careful about: in real std::vector::push_back-like code, %len is often multi-use because it is also passed to operator new. So requiring the select to have one use would miss the important case. The fold should be able to fold only the icmp to a constant when the growth amount is known non-zero, while leaving the %len value alive for the allocation-size use.
For the more general dynamic form _M_check_len(n, ...), the zero check is equivalent to:
```llvm
icmp eq/ne (or %size, %n), 0
```
but creating a new or should probably be guarded by profitability / one-use checks, because %len may still be used elsewhere.
AliveProof : https://alive2.llvm.org/ce/z/gXfEZx
Compiler-explorer sample & perf : https://compiler-explorer.com/z/MPo66zPq3
RealWorld Usage : https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/pull/405/changes
The core of this issue is the call to std::vector::push_back : https://compiler-explorer.com/z/4j7YqfzK1
and Related with : https://github.com/llvm/llvm-project/issues/170071
Contributor guide
Assessment
This issue has not been assessed yet.